c++ - 为什么 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排序 854 毫秒，随机播放 565 毫秒，clang排序 874 毫秒，随机播放 648 毫秒。 ideone 和 coliru 显示的结果更加激烈:ideone排序 1181 毫秒，随机播放 1292 毫秒 和 coliru排序 1157 毫秒，随机播放 1461 毫秒。

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

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. 每次交换使用 vector 中的一个完全随机的元素。当数据量很大时，整个 vector 无法放入 CPU 缓存，因此每次此类访问都必须等到从 RAM 中读取数据。

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