为什么 std::shuffle 和 std::sort 一样慢（甚至慢）？

Question

考虑测量执行时间和执行交换次数的简单代码：

#include <iostream>

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

struct A {
    A(int i = 0) : i(i) {}
    int i;
    static int nSwaps;

    friend void swap(A& l, A& r)
    {
        ++nSwaps;
        std::swap(l.i, r.i);
    }

    bool operator<(const A& r) const
    {
        return i < r.i;
    }
};

int A::nSwaps = 0;

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::milliseconds;


int main()
{
    std::vector<A> v(10000000);

    std::minstd_rand gen(std::random_device{}());
    std::generate(v.begin(), v.end(), [&gen]() {return gen();});

    auto s = high_resolution_clock::now();
    std::sort(v.begin(), v.end());
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";

    A::nSwaps = 0;
    s = high_resolution_clock::now();
    std::shuffle(v.begin(), v.end(), gen);
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";
}

程序的输出取决于编译器和机器，但它们在本质上非常相似。在装有 VS2015 的笔记本电脑上，我得到 1044 毫秒和 1 亿次排序交换，824 毫秒和 1000 万次随机交换。

libstdc++ 和 libc++ 进行两倍的排序交换（~50M），结果如下。 Rextester 给了我类似的结果：gcc sort 854ms, shuffle 565ms, clang sort 874ms, shuffle 648ms. The results shown by ideone and coliru are even more drastic: ideone sort 1181ms, shuffle 1292ms and coliru sort 1157ms，shuffle 1461ms。

那么这里的罪魁祸首是什么？为什么 5 到 10 倍的交换排序几乎和简单的洗牌一样快甚至更快？我什至没有考虑 std::sort 中的比较和更复杂的逻辑，包括选择插入、堆或快速排序算法等。我怀疑它是随机引擎 - 我什至选择了最简单的 std::minstd_rand 基本上进行整数乘法和模运算。是缓存未命中导致随机播放相对较慢吗？

PS：行为与简单 std::vector<int>

相同

Answer 1

首先，std::sort不需要使用不合格的swap。这不是自定义点，您不能依赖通过 ADL 找到您自己的用户定义 swap。但即便如此，sort也可以用std::rotate，可以做到swap，也可以做到memmove。这不会被您的实施计算在内。

其次，标准库只指定了渐近复杂度，对于std::shuffle是O(N)，对于std::sort是O(N log N)。因此，您应该测量 N 的不同值（例如 2 的幂从 65K 到 65M 的元素数量）并测量缩放行为。对于小 N，sort 的比例常数可能比 shuffle 的比例常数小得多，因为它必须调用一个潜在昂贵的随机生成器。

Update：看来常数因子 and/or 缓存效应确实是罪魁祸首（正如@stgatilov 所指出的）。在调用 std::shuffle 后，请参阅 this DEMO，其中我运行 std::sort 上的数据。 sort 的运行时间大约是 shuffle 的一半，交换次数多 5 倍。

Answer 2

std::random_shuffle通常工作如下：

//random(k) generates uniform random from 0 to k-1 inclusive
for (int i = 1; i < n; i++)
  swap(arr[i], arr[random(i + 1)]);

所以我们可以在这里看到两个低效率的来源：

随机数生成器通常很慢。
每次交换使用向量中的一个完全随机的元素。当数据量很大时，整个向量放不下 CPU 缓存，所以每次这样的访问都必须等到数据从 RAM 中读取出来。

说到第 2 点，像快速排序这样的排序算法对缓存更友好：它们的大部分内存访问都会命中缓存。

为什么 std::shuffle 和 std::sort 一样慢（甚至慢）？

Why is std::shuffle as slow (or even slower than) std::sort?

c++

sorting

performance

shuffle

c++11