c# - 提高 "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;
        }
    }
}

我正在寻找一种更快、更有效的方法来完成这项工作。现在，使用 Stopwatch 类，洗牌 100,000,000 个项目大约需要 20 秒。有没有人有任何想法可以使它更快？

Answer 1

这突出了现代计算机设计中经常被忽视的一个方面。通过一个愚蠢的改变，它可以快 3 倍以上:

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

现在在内循环中有更多 语句，但速度更快。您看到的是 CPU 缓存的效果。该算法的缓存局部性非常差，下一个要从数组中读取的元素已经在缓存中的可能性非常低。这需要花费昂贵的费用才能到达较慢的外部缓存和极慢的内存总线。稍后需要的数组元素被加载到缓存中的可能性非常高。但是它们在需要时仍然存在的可能性非常低，您的列表太大而无法容纳缓存。

无法解决此问题，这是算法设计中固有的。然而，使用现实的列表大小是一个显而易见的解决方案。在具有 1000 个元素的列表上运行 100,000 次是快 3 倍。