在我的算法类中,我们必须提交删除整数列表中重复项的算法,并尽可能降低复杂度。在我的算法中,当我看到一个重复的整数时,我将该整数之后的每个元素向下移动一个索引,以便使用for循环删除重复的元素;如下所示:
for(int i=dup_index; i<arr_size-1; i++) { arr[i] = arr[i+1]; }
字符串我的算法使用memmove会更有效吗?此外,如果我的工作是设计算法,并且假设memmove降低了我的算法的复杂度,那么使用memmove会被视为“作弊”吗?
iqxoj9l91#
我不知道作弊,但memmove基本上做了你的循环所做的,只是更有效。此外,它是最基本的实用功能之一,所以我不明白为什么你不应该使用它。至于复杂性,算法的顺序不会改变,它只是更快。memmove是在汇编中实现的,并试图充分利用对齐来复制每个字而不是每个字节。编辑:好吧,在某些情况下,手动复制可能比调用memmove短几条指令,但是如果你开始在内存中移动数据,你正在做一个固有的昂贵操作,所以优化几个CPU周期不会有任何影响。如果您的设计涉及对性能关键数据的就地移动,那么最好更改底层数据结构,以避免完全复制(列表,树,哈希表等)。
memmove
ukdjmx9f2#
使用memmove你的程序可能会运行得更快,但你的for循环基本上实现了同样的事情,算法复杂度不会改变。
ehxuflar3#
从功能上讲,memmove做的正是你的循环所做的。然而,编译器和/或C运行时可能会使用更有效的机器代码来实现memmove。一些架构有专门的指令,这些指令将完全在单个指令中执行这样的操作。它也可能被编译器内联。它不会改变算法的复杂性,只是让它做得更快。至于这是否会被认为是你的作业作弊-这是你的教授的问题,当然?这里没有人能告诉你。
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++; }
型
5jvtdoz25#
库函数(如memmove(3))经过了精心优化。如果你看看你最喜欢的编译器是如何将其写入汇编语言的各种长度(以常量形式给出),你可能会得到巨大的惊喜。也就是说,将$n$字节从一个地方复制到另一个地方将花费时间$\Theta(n)$,除非您知道一些有助于避免部分数据重排的方法,而不仅仅是将其减少一个固定的分数。
memmove(3)
xesrikrc6#
更新一个老答案:这些天来,毫无疑问,你最好使用内置的memmove,memcpy等,因为这些将最有可能被优化,以利用CPU的功能,如缓存和SIMD(单指令,多数据),它可以移动或复制大块的字节使用一个单一的CPU指令。
6条答案
按热度按时间iqxoj9l91#
我不知道作弊,但
memmove
基本上做了你的循环所做的,只是更有效。此外,它是最基本的实用功能之一,所以我不明白为什么你不应该使用它。
至于复杂性,算法的顺序不会改变,它只是更快。
memmove
是在汇编中实现的,并试图充分利用对齐来复制每个字而不是每个字节。编辑:
好吧,在某些情况下,手动复制可能比调用
memmove
短几条指令,但是如果你开始在内存中移动数据,你正在做一个固有的昂贵操作,所以优化几个CPU周期不会有任何影响。如果您的设计涉及对性能关键数据的就地移动,那么最好更改底层数据结构,以避免完全复制(列表,树,哈希表等)。
ukdjmx9f2#
使用memmove你的程序可能会运行得更快,但你的for循环基本上实现了同样的事情,算法复杂度不会改变。
ehxuflar3#
从功能上讲,memmove做的正是你的循环所做的。然而,编译器和/或C运行时可能会使用更有效的机器代码来实现memmove。一些架构有专门的指令,这些指令将完全在单个指令中执行这样的操作。它也可能被编译器内联。
它不会改变算法的复杂性,只是让它做得更快。
至于这是否会被认为是你的作业作弊-这是你的教授的问题,当然?这里没有人能告诉你。
ylamdve64#
如果有多个重复项,则可以使用辅助项来存储非重复项:
字符串
如果您需要inplace:-
型
5jvtdoz25#
库函数(如
memmove(3)
)经过了精心优化。如果你看看你最喜欢的编译器是如何将其写入汇编语言的各种长度(以常量形式给出),你可能会得到巨大的惊喜。也就是说,将$n$字节从一个地方复制到另一个地方将花费时间$\Theta(n)$,除非您知道一些有助于避免部分数据重排的方法,而不仅仅是将其减少一个固定的分数。
xesrikrc6#
更新一个老答案:这些天来,毫无疑问,你最好使用内置的memmove,memcpy等,因为这些将最有可能被优化,以利用CPU的功能,如缓存和SIMD(单指令,多数据),它可以移动或复制大块的字节使用一个单一的CPU指令。