2

在 CLRS 第 2 章中有一个练习，询问是否将插入排序的最坏情况运行时间改进为O(n lg n). 看到这个问题，发现做不到。

无法改善最坏情况的复杂性，但memmove与单独移动数组元素相比，使用实际运行时间会更好吗？

单独移动元素的代码

void insertion_sort(int arr[], int length)
{
    /*
    Sorts into increasing order
    For decreasing order change the comparison in for-loop
    */
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
            arr[k + 1] = arr[k];
        }
        arr[k + 1] = temp;
    }
}

使用移动元素的代码 memmove

void insertion_sort(int arr[], int length)
{
    for (int j = 1; j < length; j++)
    {
        int temp = arr[j];
        int k;
        for (k = j - 1; k >= 0 && arr[k] > temp; k--){
                ;
        }
        if (k != j - 1){
            memmove(&arr[k + 2], &arr[k + 1], sizeof(int) *(j - k - 2));
        }
        arr[k + 1] = temp;
    }
}

我无法让第二个完美运行，但这是我正在考虑做的一个例子。

使用 会有任何明显的速度改进memmove吗？

4

4 回答 4

6

后面的实现memmove()可能在您的 C 库中得到更优化。一些架构具有一次非常有效地移动整个内存块的指令。理论上的运行时间复杂度不会提高，但在现实生活中它可能仍然运行得更快。

于 2013-07-09T15:52:33.230 回答
3

memmove将被完美调整以最大限度地利用可用的系统资源（当然，对于每个实现来说都是独一无二的）。

这是Expert C Programming - Deep C Secrets关于使用循环和使用之间区别的一点引用memcpy（前面是两个代码片段，一个使用for循环将源复制到目标，另一个memcpy）：

在这种特殊情况下，源和目标都使用相同的缓存行，导致每个内存引用都错过缓存并在等待常规内存交付时停止处理器。库memcpy()例程特别针对高性能进行了调整。它展开循环以读取一个缓存行然后写入，从而避免了该问题。使用智能副本，我们能够获得巨大的性能提升。这也表明从头脑简单的基准程序中得出结论是愚蠢的。

这可以追溯到 1994 年，但它仍然说明了与您自己推出的任何东西相比，标准库函数的优化程度要好得多。循环案例运行大约需要 7 秒，而memcpy.

虽然memmove只会比memcpy由于它需要对源和目标做出的假设（memcpy因为它们不能重叠）而稍微慢一点，但它仍然应该远远优于任何标准循环。

请注意，这不会影响复杂性（正如另一位海报所指出的那样）。复杂性不取决于拥有更大的缓存或展开的循环:)

这里要求的是代码片段（略有更改）：

#include <string.h>
#define DUMBCOPY for (i = 0; i < 65536; i++) destination[i] = source[i] 

#define SMARTCOPY memcpy(destination, source, 65536) 
int main() 
{ 
    char source[65536], destination[65536]; 
    int i, j; 
    for (j = 0; j < 100; j++) 
        DUMBCOPY; /* or put SMARTCOPY here instead */
    return 0;
}

在我的机器（32 位，Linux Mint，GCC 4.6.3）上，我得到了以下时间：

使用 SMARTCOPY：

$ time ./a.out 
real    0m0.002s
user    0m0.000s
sys     0m0.000s

使用 DUMBCOPY：

$ time ./a.out 
real    0m0.050s
user    0m0.036s
sys     0m0.000s
于 2013-07-09T15:52:48.503 回答
2

这完全取决于您的编译器和其他实现细节。确实memmove可以通过一些棘手的超级优化方式来实现。但与此同时，智能编译器可能能够弄清楚您的每个元素复制代码正在做什么，并以相同（或非常相似）的方式对其进行优化。试试看，自己看看。

于 2013-07-09T16:00:40.333 回答
0

你不能用 C 实现击败 memcpy。因为它是用 asm 编写的并且具有良好的算法。

如果您考虑为特定 cpu 编写 asm 代码，并开发考虑缓存的良好算法，您可能会有机会。

标准库函数优化得非常好，使用它们总是更好。

于 2013-08-20T18:31:53.583 回答