c++ memmove是移动元素(与for循环相同),还是一次抓取整个内存块?

esbemjvw  于 11个月前  发布在  其他
关注(0)|答案(6)|浏览(94)

在我的算法类中,我们必须提交删除整数列表中重复项的算法,并尽可能降低复杂度。在我的算法中,当我看到一个重复的整数时,我将该整数之后的每个元素向下移动一个索引,以便使用for循环删除重复的元素;如下所示:

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

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

iqxoj9l9

iqxoj9l91#

我不知道作弊,但memmove基本上做了你的循环所做的,只是更有效。
此外,它是最基本的实用功能之一,所以我不明白为什么你不应该使用它。
至于复杂性,算法的顺序不会改变,它只是更快。memmove是在汇编中实现的,并试图充分利用对齐来复制每个字而不是每个字节。
编辑:
好吧,在某些情况下,手动复制可能比调用memmove短几条指令,但是如果你开始在内存中移动数据,你正在做一个固有的昂贵操作,所以优化几个CPU周期不会有任何影响。
如果您的设计涉及对性能关键数据的就地移动,那么最好更改底层数据结构,以避免完全复制(列表,树,哈希表等)。

ukdjmx9f

ukdjmx9f2#

使用memmove你的程序可能会运行得更快,但你的for循环基本上实现了同样的事情,算法复杂度不会改变。

ehxuflar

ehxuflar3#

从功能上讲,memmove做的正是你的循环所做的。然而,编译器和/或C运行时可能会使用更有效的机器代码来实现memmove。一些架构有专门的指令,这些指令将完全在单个指令中执行这样的操作。它也可能被编译器内联。
它不会改变算法的复杂性,只是让它做得更快。
至于这是否会被认为是你的作业作弊-这是你的教授的问题,当然?这里没有人能告诉你。

ylamdve6

ylamdve64#

如果有多个重复项,则可以使用辅助项来存储非重复项:

int aux[arr_size],cnt=0;

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

   if(arr[i]!=dup) {

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

字符串

如果您需要inplace:-

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

}

5jvtdoz2

5jvtdoz25#

库函数(如memmove(3))经过了精心优化。如果你看看你最喜欢的编译器是如何将其写入汇编语言的各种长度(以常量形式给出),你可能会得到巨大的惊喜。
也就是说,将$n$字节从一个地方复制到另一个地方将花费时间$\Theta(n)$,除非您知道一些有助于避免部分数据重排的方法,而不仅仅是将其减少一个固定的分数。

xesrikrc

xesrikrc6#

更新一个老答案:这些天来,毫无疑问,你最好使用内置的memmove,memcpy等,因为这些将最有可能被优化,以利用CPU的功能,如缓存和SIMD(单指令,多数据),它可以移动或复制大块的字节使用一个单一的CPU指令。

相关问题