提高"洗牌"效率

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;
        }
    }
}

我正在寻找一种更快,更有效的方法来做到这一点.现在,使用秒表类,大约需要20秒来洗牌100,000,000件物品.有没有人有任何想法让这更快？

Answer 1

这凸显了现代计算机设计中经常被忽视的一个方面。通过一个愚蠢的改变可以使其速度提高 3 倍以上：

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

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

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