为什么 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。ideone 和coliru 显示的结果更加剧烈：ideone sort 1181ms , shuffle 1292ms和coliru sort 1157ms , shuffle 1461ms。

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

PS：简单的行为是相同的 std::vector<int>

Answer 1

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)]);

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

1. 随机数生成器通常很慢。
2. 每个交换使用向量中的一个完全随机的元素。当数据量很大时，整个向量不适合 CPU 缓存，因此每次这样的访问都必须等到从 RAM 中读取数据。

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