如何工作 realloc 和 memcpy?
我有两个问题。
复制谎言
和
阵列中的条目速度快于每个元素的迭代
? 如果答案 "是的", 然后,在您看来,它的复杂性 ?
如果所选尺寸小于源,则被复制
在另一个地方的条目或简单地将它们留下,因为阵列的大小减少 ?
复制谎言
realloc//
和
memcpy//
阵列中的条目速度快于每个元素的迭代
O/N/
? 如果答案 "是的", 然后,在您看来,它的复杂性 ?
如果所选尺寸小于源,则被复制
realloc//
在另一个地方的条目或简单地将它们留下,因为阵列的大小减少 ?
没有找到相关结果
已邀请:
8 个回复
裸奔
赞同来自:
http://www.embedded.com/design ... speed
对于一个非常好的分析。
2这取决于实施。 看
http://www.gnu.org/software/li ... .html
为了 glibc 细节。 "在若干分发实现中,块大小有时会减少需要复制它。"
快网
赞同来自:
而我们在它上面,在 "big O" 或Landau指定。
首先, big-O. 正如我在另一个地方所说,值得记住定义 big O, 这是一些功能的事实
g/n/
叫
O/f/n//
, 当有一个常数
k
, 对于那么
g/n/
≤
kf/n/
. 常量允许您忽略小细节,以支持重要的部分。 每个人都有人注意到
的
n
字节将是
O /n/
在大多数普通的架构中,因为无论你需要移动这些问题
n
字节,一次一件。 因此,第一,天真的实现
在 C 可能是书面的
实际上它
O/n/
, 你可以想知道为什么我们都担心图书馆例程。 但是,功能的特征
libc
在于它们是一个用于特定平台的公用事业的地方; 如果要优化架构,这是您可以执行的地方之一。 因此 , 在
取决于架构
, 可能有更有效的实施方案; 例如,在archharochitecture中 IBM 360 有一个指示
, 其中通过非常优化的微码将数据移动到大块。 因此,而不是循环实现 memcpy 360 可能看起来像这样
/顺便说一下,没有保证这正是代码。 360, 但他是一个插图。/ 这个实施
看起来像
所以不是在做
n
循环周围的步骤,代码是如此 C, 她只是表演了 3 指示。
但是,在非常
商业
他表演会发生什么
o/n/ 微量分泌物
在毯子下面。 什么
是不同的
它们之间的两个是常数
k
; 由于微码更快,并且由于指令中只有三个解码步骤,因此他
很多
比天真的版本更快,但它仍然是
O/n/
- 只是一个不变的少。
这就是为什么你可以很好地使用
- 它不是渐近的速度更快,但实施是如此迅速,因为有人可以做到这一点
在这个特定的架构上
.
董宝中
赞同来自:
我肯定不知道,但我建议内存完全重新分配。 这是最安全的假设,并且可能取决于任何情况下的实现。
小明明
赞同来自:
实际上不能好 O/N/, 但它可以优化,以便超过手动复制; 例如,它可以复制 4 在您需要复制时的字节 1 字节。 许多实现
写在 assembly 使用可以同时复制多个项目的优化指令,该指令通常比一次一个字节复制数据更快。
如果你使用,我不太了解这个问题
减少记忆的大小,他成功 /返回NE. NULL/, 一个新的位置将包含与旧位置相同的数据,最多为新请求的大小。 如果由于呼叫而改变了存储器单元
/通常不会在减少尺寸时/, 内容将被复制,否则不需要复制,因为内存尚未移动。
二哥
赞同来自:
如上所述,它不会比 O/n/, 但是,内存系统通常具有优选的块大小,并且您也可以说,一次写下缓存行的大小。
裸奔
赞同来自:
http://sourceware.org/cgi-bin/ ... glibc
http://sourceware.org/cgi-bin/ ... glibc
通过阅读它的方式来判断,答案将如下::
O /N/ - - - 没有办法比线性时间更好地复制物品。
有时,大量元素将被复制 realloc// 用来压缩它们。
快网
赞同来自:
那些用来复制的人 mem, - 这是 movsb/movsw 结合说明 rep.
使用地址设置寄存器 src/trg 和 int count, 你离开了。
涵秋
赞同来自:
空虚 *realloc/void *ptr, 尺寸 size_t /;
功能 realloc// 必须调整内存对象的大小指示 ptr, 关于指定的大小 size.
受试者的内容必须保持不变,以更小于新的和旧尺寸。
如果新尺寸较大,则未定义新选择的对象的内容的内容。
如果大小相等 0 和 ptr 不是指针 null, 它指示的对象被释放。
如果一个 ptr 是一个指针 null, 那 realloc// 必须等同 malloc// 对于指定的大小。
如果一个 ptr 与之前返回的指针不匹配 calloc//, malloc// 或者 realloc//, 或者如果以前通过呼叫发布了空间 free// 或者 realloc//, 行为绝不肯定。