为什么std::shuffle的速度很慢（甚至比std::sort还要慢）？

Question

为什么std::shuffle的速度很慢（甚至比std::sort还要慢）？

5

考虑一个简单的代码，它可以测量执行时间和交换操作的数量：

#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`，表现也是一样的。

- Rostislav

1

可能值得测量一下，其中有多少时间被约1000万个随机数生成所占用。 - Sander De Dycker

@SanderDeDycker 很好的观点。但 Ideone 报告只有 71 毫秒。 - Rostislav

这些是非常不同的工作。我不确定任何比较是否有效。std::shuffle 将严重依赖于随机数生成算法。我认为交换非常便宜，比较两个值 a < b 也很便宜。然而，生成随机数必须涉及比 a < b 更多的处理步骤。 - Galik

在我的笔记本电脑上，gcc 给出的结果为：未优化[使用46947242次交换4109毫秒，使用9999999次交换1318毫秒，使用9999999 rng375毫秒]，使用'-O2' [使用46992015次交换794 毫秒，使用9999999次交换461毫秒，使用9999999个 rng 194ms]。这两者对我来说看起来非常合理（忽略用于 rng 的时间，其差异是3-4倍，非常接近交换数量的4-5倍差异）-也就是说，我无法在这里复制您的结果。 - Sander De Dycker

你是用 Release 配置编译了吗？我用 VS2013 编译了 Release 版本，结果是：94135436 次交换用时 1005ms，9999999 次交换用时 733ms。我运行了多次得到的结果都一样：shuffle 更快。 - Matt

显示剩余3条评论

2个回答

2

首先，std::sort并不要求使用未经限定的swap。它不是一个自定义点，您不能依赖于自己定义的用户swap通过ADL找到。但是即使如此，sort也可以使用std::rotate，它可以执行swap，但也可以执行memmove。这将不会被您的实现计算在内。

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

更新：确实似乎是恒定因素和/或缓存效应是罪魁祸首（正如@stgatilov所指出的）。请参见此演示，在此演示中，我对std::shuffle调用后的数据运行std::sort。 sort的运行时间约为shuffle的一半，并进行了5倍的交换。

- TemplateRex

然而，问题在于，除非shuffle在某些情况下不使用swap，否则至少5的比率仍然存在，因此sort可能会比我用简单指标捕捉不到的shuffle做更多的工作。然而，它相对较快。这让我感到困惑，但似乎缓存友好性是关键。 - Rostislav

@Rostislav，为了真正隔离缓存效应，为什么不在数据“洗牌”之后测量sort呢？因此，使用iota（数字0到100M）生成数据，然后测量shuffle，再测量sort。然后您可以保证两种算法具有相同的缓存局部性效应。 - TemplateRex

好主意！一到电脑前我就试试。如果有什么问题，我觉得它甚至会更受欢迎 :) 同时我的感觉可能是错的 - 测量才是王道... - Rostislav

2

std::sort 允许通过ADL（关联名称查找）调用客户端的 swap，实现移动构造和移动赋值操作。一个简单但合法的实现可以只调用 std::swap（不使用ADL），因为 std::swap 仅允许调用移动构造和移动赋值操作。std::shuffle 仅允许通过ADL调用 swap（如果没有自定义的 swap，则可能会解析为 std::swap）。在所有情况下，swap 都是一个“定制化点”。 - Howard Hinnant

1

这就是使用标准中没有官方定义的术语的问题。:-) 我认为swap是一个定制点，因为它可以是std算法的自定义替代品。但是标准没有使用这个术语。它使用诸如：“shuffle需要Swappable”。然后，Swappable被严格定义为：如果您有自定义的swap，则调用它，否则调用std::swap。一些算法（例如sort）说（我在这里简述）：需要Swappable、MoveConstructible和MoveAssignable。允许使用任何/所有这些，而不使用其他任何东西。 - Howard Hinnant

显示剩余5条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stgatilov · Accepted Answer

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读取数据。

关于第二点，像快速排序这样的排序算法更加适合缓存：它们的大多数内存访问都命中缓存。