c - realloc 和 memcpy 如何工作？

Question

我有两个问题。

1. realloc() 和 memcpy() 将一个数组中的条目复制到另一个数组中，其速度比仅迭代每个元素快 O (N) ?如果答案是肯定的，那么您认为它的复杂性是什么？

2. 如果分配的大小小于原始大小，realloc() 是将条目复制到其他地方还是在它们减小数组大小时保留它们？

Answer 1

让我们仔细看看 memcpy 以及“大 O”或 Landau 表示法。

首先，大O。正如我在别处谈到的，值得记住大 O 的定义，即某些函数 g(n) 被称为 O(f(n)) 当存在 k 且 g(n) ≤ kf(n) 时。常量的作用是让您忽略小细节而关注重要部分。正如每个人都注意到的，n 字节的 memcpy 在大多数正常架构中都是 O(n)，因为无论您必须移动什么那些 n 字节，一次一个 block 。因此，可以用 C 编写 memcpy 的第一个简单实现

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

这实际上是 O(n)，您可能想知道为什么我们还要为库例程烦恼。然而，关于 libc 函数的事情是它们是编写特定于平台的实用程序的地方；如果你想优化架构，这是你可以做的地方之一。因此，根据架构，可能会有更高效的实现方案；例如，在 IBM 360 架构中，有一条 MOVL 指令使用高度优化的微码移动大块数据。因此，代替该循环，memcpy 的 360 实现可能看起来像

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(顺便说一下，不能保证 360 度代码完全正确，但它可以用作说明。)此实现看起来而不是执行 n 个步骤像 C 代码那样循环，它只执行 3 条指令。

不过，真正 发生的是它在幕后执行O(n) 微 指令。两者之间的不同是常量k；因为微代码要快得多，而且因为指令上只有三个解码步骤，所以它比原始版本快显着，但它仍然是O(n) --只是常数变小了。

这就是您可以充分利用 memcpy 的原因——它的速度并没有渐进式加快，但实现速度与某人在特定架构上 所能达到的速度一样快。