memmove 是否会移位元素（与 for 循环的方式相同），还是会立即获取整个内存块？

Question

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

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

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

Answer 1

我不知道作弊，但是

memmove

基本上做了你的循环所做的事情，只是效率更高。

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

至于复杂度，算法的顺序不会改变，只是更快。

memmove

在汇编中实现，并尝试充分利用对齐方式逐字复制而不是逐字节复制。

编辑：

好吧，在某些情况下，手动复制可能比调用

memmove

短一些指令，但是如果您开始在内存中移动数据，那么您正在执行本质上成本高昂的操作，因此需要优化一些指令CPU 周期的消失不会对整体产生任何影响。

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

Answer 2

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

Answer 3

从功能上来说，memmove 的作用与循环的作用完全相同。然而，编译器和/或 C 运行时可以使用更高效的机器代码来实现 memmove。一些体系结构具有专门的指令，它们将完全在单个指令中执行此类操作。它也可能被编译器内联。

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

至于你的作业是否会被视为作弊——这当然是你的教授的问题吗？这里没有人可以告诉你这一点。

Answer 4

如果有多个重复项，您可以使用辅助设备来存储非重复项:-

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++;

}

Answer 5

库函数（如

memmove(3)

）经过精心优化。如果您查看您最喜欢的编译器如何将其以各种长度（以常量形式给出）写入汇编语言，您可能会大吃一惊。

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

Answer 6

更新旧答案：毫无疑问，现在使用内置 memmove、memcpy 等会更好，因为这些很可能会被优化以利用缓存和 SIMD（单指令、多数据）等 CPU 功能，它可以使用单个 CPU 指令移动或复制大块字节。