提高“shuffle”效率

Question

目前，我正在使用以下代码创建一个Shuffle扩展：

public static class SiteItemExtensions
{
    public static void Shuffle<T>(this IList<T> list)
    {
        var rng = new Random();
        int n = list.Count;
        while (n > 1)
        {
            n--;
            int k = rng.Next(n + 1);
            T value = list[k];
            list[k] = list[n];
            list[n] = value;
        }
    }
}

我正在寻找一种更快、更高效的方法来完成这个任务。目前使用计时器类，对于100,000,000个项目进行洗牌需要大约20秒钟。是否有任何想法可以使这个过程更快？

- Icemanind

---

你为什么要对1亿项进行洗牌？你能否通过某种方式减少这个数字？ - dlev

这里给出的算法不会产生均匀分布。一个简单的计数论证可以证明这一点。这个算法只使用32位种子进行随机选择，因此最多只能生成2^32个可能的序列。但是当n大于32时，可能的洗牌次数超过了2^32。因此，有些洗牌顺序将不会被该算法生成，因此分布不是均匀的。 - Eric Lippert

不，这是一种费舍尔耶茨洗牌算法：http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm - Hans Passant

@HansPassant：不，我说的是这里介绍的算法。如果随机源的熵不足，则Knuth洗牌算法无法给出无偏置的洗牌结果。由于这里的随机源最多只有32位熵，因此它不可能给超过32个项目的无偏置洗牌结果，因为32！ > 2^32。 - Eric Lippert

new Random(); 每次调用都不好。 - paparazzo

Answer 1

这突显了现代计算机设计中常被忽视的一个方面。通过一个不起眼的改变，它可以提高3倍以上的速度：

            int k = 0; rng.Next(n + 1);  // silly change

现在内部循环中有更多的语句，但速度更快。这是CPU缓存的影响。该算法的缓存局部性非常差，从数组中读取下一个元素已经在缓存中的概率非常低。需要进行昂贵的访问外部缓存和非常慢的内存总线。需要后面的数组元素加载到缓存中的概率非常高。但需要时它们仍然存在于缓存中的概率非常低，因为列表太大而无法适应缓存。

无法解决这个问题，这是算法设计的固有问题。然而，使用适当大小的列表是一个明显的解决方案。在一个包含1000个元素的列表上运行100,000次会快3倍。

- Hans Passant

---

你真的想要使用 int k = 0; rng.Next(n + 1) 吗？ - Paul Walls

那么速度的提升是因为存储指令每次都使用缓存值0而不是在rng.Next(n + 1)中进行失败查找吗？（我意识到这与OP的问题无关，但我对这个结果非常着迷。） - Paul Walls

这是因为它现在一直使用相同的内存地址而不是随机的地址，所以该值保证在快速缓存中。 - Hans Passant

啊...所以你提到列表大小导致缓存局部性不佳。谢谢解释。 - Paul Walls

好的，不，算法的缓存局部性很差是确定的。列表大小使其对性能具有致命影响。在适合缓存的小列表上，愚蠢版本与常规版本一样快。 - Hans Passant

@HansPassant -- 我觉得这很有趣。我想再保持一段时间以保持问题的开放性，看看是否还有更多回应，但到目前为止，我喜欢你的答案。 - Icemanind

Answer 2

你已经超过了CPU缓存的能力，大部分时间都在等待RAM。

通过逐步降低元素数量，我得到了以下结果（在 List<int> 上）：

count      time (s)     slowdown
100000000  16.0429005   11.99215276436421
10000000   01.3377832   20.37312930505406
1000000    00.0656641   13.36837069158574
100000     00.0049119

注意在10^6和10^7之间出现的明显减速。我将元素数量增加了10倍，但时间增加了20倍。这可能是因为我的CPU不能将大部分数组放入第二个（也是最后一个）缓存级别中。顺便说一下，通过在方法签名中使用List<T>替换IList<T>并避免在[]上进行接口调用惩罚，可以节省一两秒钟（但会失去通用性）。

IList<T>:   16.0429005 s
List<T>:    14.3529349 s

记录一下，在Visual C++ 2010下，对于包含100000000个元素的std::vector<int>使用std::random_shuffle需要...

17.947 s

如果您已经尽力了，那么您可能已经达到了最快的速度。

（注意：C＃和C ++基准测试都是在各自的发布配置下，在调试器之外完成的。）

- Branko Dimitrijevic