手写快速排序在较小的整数上速度较慢

Question

比较我的快速排序实现和C++ STL库的std::sort，在我的编译器上测试，以及我的归并排序实现，在处理大数据集合时，我注意到一个奇怪的规律：当处理64位整数时，快速排序始终比归并排序快；但是，当处理小于64位的整数时，反而快速排序变慢了，而归并排序变得更快。

下面是测试代码：

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <utility>
#include <random>
#include <chrono>
#include <limits>
#include <functional>

#include <cstdint>


template <typename Iterator>
void insertion_sort(Iterator first, Iterator last)
{
    using namespace std;

    Iterator head = first;
    Iterator new_position;

    while(head != last)
    {
        new_position = head;
        while(new_position != first && *new_position < *prev(new_position))
        {
            swap(*new_position, *prev(new_position));
            --new_position;
        }
        ++head;
    }
}

template <typename Iterator>
void recursive_mergesort_impl(Iterator first, Iterator last, std::vector<typename Iterator::value_type>& temp)
{
    if(last - first > 32)
    {
        auto middle = first + (last-first)/2;
        recursive_mergesort_impl(first, middle, temp);
        recursive_mergesort_impl(middle, last, temp);
        auto last_merged = merge_move(first, middle, middle, last, temp.begin());
        std::move(temp.begin(), last_merged, first);
    }
    else
    {
        insertion_sort(first, last);
    }
}

template <typename Iterator>
void recursive_mergesort(Iterator first, Iterator last)
{
    std::vector<typename Iterator::value_type> temp(last-first);
    recursive_mergesort_impl(first, last, temp);
}

// Pick a pivot and move it to front of range
template <typename Iterator>
template <typename Iterator>
void quicksort_pivot_back(Iterator first, Iterator last)
{
    using namespace std;

    auto middle = first + (last-first)/2;
    auto last_elem = prev(last);
    Iterator pivot;

    if(*first < *middle)
    {
        if(*middle < *last_elem)
            pivot = middle;
        else if(*first < *last_elem)
            pivot = last_elem;
        else
            pivot = first;
    }
    else if(*first < *last_elem)
        pivot = first;
    else if(*middle < *last_elem)
        pivot = last_elem;
    else
        pivot = middle;

    swap(*last_elem, *pivot);
}

template <typename Iterator, typename Function>
std::pair<Iterator, Iterator> quicksort_partition(Iterator first, Iterator last, Function pivot_select)
{
    using namespace std;

    pivot_select(first, last);

    auto pivot = prev(last);
    auto bottom = first;
    auto top = pivot;

    while(bottom != top)
    {
        if(*bottom < *pivot) ++bottom;
        else swap(*bottom, *--top);
    }

    swap(*pivot, *top++);

    return make_pair(bottom, top);
}

template <typename Iterator>
void quicksort_loop(Iterator first, Iterator last)
{
    using namespace std;

    while(last - first > 32)
    {
        auto bounds = quicksort_partition(first, last, quicksort_pivot_back<Iterator>);

        quicksort_loop(bounds.second, last);
        last = bounds.first;
    }
}


template <typename Iterator>
void quicksort(Iterator first, Iterator last)
{
    quicksort_loop(first, last);
    insertion_sort(first, last);
}

template <typename IntType = uint64_t, typename Duration = std::chrono::microseconds, typename Timer = std::chrono::high_resolution_clock, typename Function, typename Generator>
void run_trial(Function sort_func, Generator gen, std::string name, std::size_t trial_size, std::size_t trial_count)
{
    using namespace std;
    using namespace chrono;

    vector<IntType> data(trial_size);

    Duration elapsed(0);

    cout << "Sorting with " << name << endl;

    for(unsigned int i = 0; i < trial_count; ++i)
    {
        generate(data.begin(), data.end(), gen);

        auto start = Timer::now();
        sort_func(data.begin(), data.end());
        auto finish = Timer::now();

        elapsed += duration_cast<Duration>(finish-start);
    }

    cout << "Done. Average elapsed time: " << elapsed.count() / trial_count << endl;
    cout << "Is correct: " << is_sorted(data.begin(), data.end()) << endl << endl;
}

int main()
{
    using namespace std;
    using namespace chrono;

    using int_type = uint64_t;
    const size_t trial_size = 12800000;
    const int trial_count = 15;

    vector<int_type> data(trial_size);
    uniform_int_distribution<int_type> distr;
    mt19937_64 rnd;

    run_trial<int_type>(recursive_mergesort<vector<int_type>::iterator>, bind(distr, rnd), "recursive mergesort", trial_size, trial_count);
    run_trial<int_type>(quicksort<vector<int_type>::iterator>, bind(distr, rnd), "quicksort", trial_size, trial_count);
    run_trial<int_type>(sort<vector<int_type>::iterator>, bind(distr, rnd), "std::sort", trial_size, trial_count);
}

以下是12800000个元素进行15次测试的时间:

uint64_t:

Sorting with recursive mergesort
Done. Average elapsed time: 1725431
Is correct: 1

Sorting with quicksort
Done. Average elapsed time: 1238070
Is correct: 1

Sorting with std::sort
Done. Average elapsed time: 1131464
Is correct: 1

uint16_t:

Sorting with recursive mergesort
Done. Average elapsed time: 1186467
Is correct: 1

Sorting with quicksort
Done. Average elapsed time: 2368535
Is correct: 1

Sorting with std::sort
Done. Average elapsed time: 888517
Is correct: 1

我感觉问题与未对齐的内存访问有关，但这仍然让我想知道为什么其他算法加速了而快速排序却减慢了。

- chbaker0

---

“为什么会这样呢？” 因为你的测量结果不够显著！使用性能分析工具或对大量调用进行统计测量（> 1000）。 - πάντα ῥεῖ

@πάνταῥεῖ 我知道，我知道 :) 我运行了几次并得到了相同的结果。不过我想我会让测试更全面一些，以确保结果正确。 - chbaker0

如果您重复运行程序，那样做无法以统计上可靠的方式进行测量。 - πάντα ῥεῖ

你的一次编辑将 quicksort_pivot_front() 的调用更改为 quicksort_pivot_back()，但你忘记添加该实现。 - Blastfurnace

将来您可能会让 pivot_select() 函数仅返回一个迭代器，让调用者决定是否交换或复制该值。 - Blastfurnace

Answer 1

使用 uint16_t 类型，在这么大的数组中，你将会得到很多重复的元素：在期望情况下，每个 0 到 65535 的数字都会出现 195 次。如果没有使用三向（"胖"）划分，或者至少不返回处理子数组中枢值重复出现的 中间位置，这会导致快速排序算法变成二次方级别的。 （尝试在只有零的数组上手动执行一个简单的快速排序以查看效果。）

- Fred Foo

---

+1 太棒了，我没想到那个。在决定接受哪个答案之前，我会等待看看其他的回答。这个问题是否也可以通过更好的枢轴选择来解决？ - chbaker0

@mebob：请注意，这个假设是可以被测试的，通过对同一组值进行排序，一次存储为16位，一次存储为64位。更好的枢轴选择也无济于事。问题在于经过足够多次递归后，子范围内的所有值都是相同的。三路快排是正确的选择。 - user180326

@mebob：不，改变枢轴是不够的。全零情况再次作为一个例子：枢轴始终是相同的值。 - Fred Foo