考虑一个简单的代码,它可以测量执行时间和交换操作的数量:
程序的输出取决于编译器和计算机,但它们在本质上非常相似。在我的笔记本电脑上使用VS2015,我对sort进行了1亿次交换,用时1044毫秒,对shuffle进行了1000万次交换,用时824毫秒。 libstdc++和libc++对sort进行的交换次数减少了一半(约为5000万次),结果如下所示。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倍的交换后,sort几乎和简单的shuffle一样快甚至更快?我甚至没有考虑`std::sort`中包括插入、堆或快速排序算法等更复杂的逻辑和比较。我怀疑这不是由随机引擎引起的——我甚至选择了最简单的一个`std::minstd_rand`,它基本上只执行一个整数乘法和一个取模操作。是缓存缺失使得shuffle相对较慢吗?
PS:对于简单的`std::vector`,表现也是一样的。
#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,我对sort进行了1亿次交换,用时1044毫秒,对shuffle进行了1000万次交换,用时824毫秒。 libstdc++和libc++对sort进行的交换次数减少了一半(约为5000万次),结果如下所示。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倍的交换后,sort几乎和简单的shuffle一样快甚至更快?我甚至没有考虑`std::sort`中包括插入、堆或快速排序算法等更复杂的逻辑和比较。我怀疑这不是由随机引擎引起的——我甚至选择了最简单的一个`std::minstd_rand`,它基本上只执行一个整数乘法和一个取模操作。是缓存缺失使得shuffle相对较慢吗?
PS:对于简单的`std::vector`,表现也是一样的。
std::shuffle
将严重依赖于随机数生成算法。我认为交换非常便宜,比较两个值a < b
也很便宜。然而,生成随机数必须涉及比a < b
更多的处理步骤。 - Galik