MergeSort性能

Question

您看到以下代码的任何低效部分吗？在互联网上，我看到了100.000个整数的30毫秒，但我可以在300毫秒内对100.000个整数进行排序。数据是随机的。我正在使用2013年底的macbook，所以我预计CPU不会减少10倍，但谁知道呢。

void mergesort2(int* list, int begin, int end,int *tmplist=0){
    bool allocated = false;
    if (end-begin < 1) {
        return;
    }
    if (tmplist == 0) {
        allocated = true;
        tmplist = new int[end-begin+1];
    }

    int middle = (begin+end)/2;

    mergesort2(list, begin, middle, tmplist);
    mergesort2(list, middle+1, end, tmplist);

    for (int first=begin, second=middle+1, tmp=0; tmp<end-begin+1; tmp++) {
        if (first > middle) {

            memcpy(tmplist+tmp, list+second, sizeof(int)*(end-begin-tmp+1));
        }
        else if (second > end) {
            memcpy(tmplist+tmp, list+first, sizeof(int)*(end-begin-tmp+1));

        }
        else if (list[first] <= list[second]) {
            tmplist[tmp] = list[first++];
        }else{
            tmplist[tmp] = list[second++];
        }
    }

    memcpy(list+begin, tmplist, (end-begin+1)*sizeof(int));

    if (allocated) {
        delete tmplist;
    }
}

Answer 1

标准库算法样式的C++合并排序可以编写为

template<class BiDirIt, class Compare = std::less<typename std::iterator_traits<BiDirIt>::value_type>>
void merge_sort(BiDirIt first, BiDirIt last, Compare cmp = Compare())
{
        auto const N = std::distance(first, last);
        if (N < 2) return;
        auto middle = std::next(first, N / 2);
        merge_sort(first, middle, cmp);
        merge_sort(middle, last, cmp);
        std::inplace_merge(first, middle, last, cmp);
}

让我们看看这如何改进您的设计：

• 泛型接口:它需要两个迭代器和任意类型的比较函数，而不是两个指向int数组和隐式但固定的<比较的指针的索引。
• 就地:它在封面后面调用std::inplace_merge，它可以分配额外的内存，但是它可以这样做，这样用户就不必提供这个，而不必提供tmplist参数。
• 半开放间隔:它会将输入范围[first, last)划分为[first, middle)和[middle, last)，这会自动处理middle + 1等代码中容易发生的“逐个”错误(在您的代码中，它是正确的，但您仍然需要考虑，半开放的间隔更容易纠正)。
• 命名算法:它使用std::inplace_merge作为一个可以随时使用的组件，而不是算法中的一个比较长、当然也很棘手的最后一步。这不仅使您的merge_sort更紧凑，inplace_merge本身本身也是一个可修复的组件！
• 高度优化:标准库专家很可能了解编写性能优化算法的最新状况。与代码相比，10的性能因素似乎很多，但是如果您忘记了一些隐藏的副本，可以使用一个具有O(N^2)复杂性的手写循环，而不是O(N log N)，这样您就可以快速到达那里。

Answer 2

回到最初的问题，我创建了一个用于测试您的代码的小型测试工具(毕竟，必须首先确认它确实有效！)

#define NUM_OF_INTS 100000
#define DEBUG 0
int main()
{
    int numbers[NUM_OF_INTS]; 
    int i;
    int *tmplist;

    tmplist = new int[NUM_OF_INTS];

    srand(0);

    for( i = 0; i < NUM_OF_INTS; i++ )
      numbers[i] = rand()%10000;

    if (DEBUG == 1)
    for( i = 0; i < NUM_OF_INTS; i++ )
        printf( "%03i:%04i\n", i, numbers[i] ); 

    mergesort2( &numbers[0], 0, NUM_OF_INTS, tmplist );

    if (DEBUG == 1 ) printf( "\n"); 

    if (DEBUG == 1)
    for( i = 0; i < NUM_OF_INTS; i++ )
        printf( "%03i:%04i\n", i, numbers[i] ); 

    return 0;
}

在我的环境中运行这个测试夹具，我看到了关于100 k ints的.7s。最初，我认为在每个递归迭代中检查tmplist可能会导致性能下降，但它在执行时间上的变化微不足道。然后，我开始了在没有临时数组的情况下重新实现mergesort的路径，当我偶然发现您的代码有什么问题时，我认为数组内存副本可能是性能问题的根本原因。

提示

• 想想为什么memcpy在for循环中存在。他们的目的是什么？为什么有这个必要？当那些memcpy完成执行时，算法上意味着什么？接下来会发生什么呢？

破坏者(仔细考虑和测试你的代码，然后再看这个)

对于两个退化情况，您需要做一个break;来在每个mem拷贝之后退出for循环(第一步超过中点，中间向前推进超过结束)。否则，您正在重复执行内存(幸运或不幸运，对输出没有影响)，直到tmp最终到达终点。

通过修复，代码现在可以在我的环境中在.08s中完成100 k的in，因此您需要进行10倍的改进。