c++ - memmove 是否移动元素（与 for 循环相同），还是一次抓取整个内存块？

Question

在我的算法课中，我们必须上交用于删除整数列表重复项的算法，并尽可能降低复杂度。在我的算法中，当我看到一个重复的整数时，我将该整数之后的每个元素向下移动一个索引，以便使用 for 循环删除重复的元素；像这样：

for(int i=dup_index; i<arr_size-1; i++)
{
  arr[i] = arr[i+1];
}

我的算法使用 memmove 会更有效吗？此外，如果设计算法是我的工作，并且假设 memmove 降低了我的算法的复杂性，那么使用 memmove 会被视为“作弊”吗？

score 2 · Accepted Answer

我不知道作弊，但memmove基本上做你的循环所做的，只是更有效。

此外，它是最基本的实用功能之一，所以我不明白你为什么不应该使用它。

至于复杂度，算法的顺序不会改变，只会更快。memmove在汇编中实现，并试图充分利用对齐来逐字复制而不是逐字节复制。

编辑：

好吧，在某些情况下，手动复制可能比对的调用短一些指令memmove，但是如果你开始在内存中移动数据，你正在做一个固有的昂贵的操作，所以优化几个 CPU 周期不会对大局产生任何影响。

如果您的设计涉及性能关键数据的就地移动，您最好更改底层数据结构以完全避免复制（列表、树、哈希表等）。

score 0 · Accepted Answer

就挂钟时间而言，您的程序使用 memmove 可能会运行得更快，但您的 for 循环基本上可以实现相同的目标。算法复杂度不会改变。

score 0 · Accepted Answer

从功能上讲，memmove 完全符合您的循环所做的工作。但是，编译器和/或 C 运行时可以使用更高效的机器代码来实现 memmove。一些架构具有专门的指令，这些指令将完全在单个指令中执行此类操作。它也可以由编译器内联。

它不会改变算法的复杂性，它只是让它更快地完成。

至于它是否会被视为在你的作业中作弊——这当然是你的教授的问题吗？这里没有人能告诉你。

score 0 · Accepted Answer

如果有多个重复项，则可以使用辅助存储非重复项：-

int aux[arr_size],cnt=0;

for(int i=0;i<arr_size;i++) {

   if(arr[i]!=dup) {

         aux[cnt++] = arr[i];
   }
}

如果您需要就地：-

int i = dup_index;
int j = dup_index+1;
int dup = arr[i];

while(j<arr_size) {

  if(arr[j]!=dup) {

      arr[i++] = arr[j];

  }

  j++;

}

score 0 · Accepted Answer

库函数（如memmove(3)）经过精心优化。如果你看看你最喜欢的编译器如何将它写成各种长度的汇编语言（以常量形式给出），你可能会大吃一惊。

也就是说，将 $n$ 个字节从一个地方复制到另一个地方将花费时间 $\Theta(n)$，除非您知道一些有助于避免部分混洗数据的东西，而不仅仅是将其减少一个固定的分数.

5 回答 5