使用Random和OrderBy是一个很好的shuffle算法吗？

Question

我在Coding Horror上读过一篇关于各种shuffle算法的文章.我已经看到人们已经在某个地方对列表进行了洗牌:

var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());

这是一个很好的shuffle算法吗？它是如何工作的？这样做是否可以接受？

Answer 1

这不是一种我喜欢的洗牌方式,主要是因为它很容易实现O(n)shuffle,这是O(n log n)的理由.问题中的代码"工作"基本上给每个元素一个随机(希望是唯一的!)数字,然后根据该数字排序元素.

我更喜欢Durstenfield的Fisher-Yates shuffle变体,它可以交换元素.

实现一个简单的Shuffle扩展方法基本上包括调用ToList或ToArray输入然后使用Fisher-Yates的现有实现.(Random作为参数传递,使生活更加美好.)周围有很多实现......我可能在某个地方有一个答案.

这种扩展方法的好处是,读者可以非常清楚你实际上要做什么.

编辑:这是一个简单的实现(没有错误检查!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

编辑:下面的性能评论提醒我,我们可以在我们洗牌时实际返回元素:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

现在,这只能完成所需的工作量.

请注意,在这两种情况下,您都需要注意Random使用的实例:

• Random在大致相同的时间创建两个实例将产生相同的随机数序列(当以相同的方式使用时)
• Random 不是线程安全的.

我有一篇文章Random详细介绍了这些问题并提供了解决方案.

Answer 2

这是基于Jon Skeet的回答.

在那个答案中,数组被洗牌,然后使用返回yield.最终的结果是数组在foreach的持续时间内保存在内存中,以及迭代所需的对象,但成本都在开始时 - yield基本上是一个空循环.

该算法在游戏中被大量使用,其中前三个项目被选中,而其他项目仅在以后才需要.我的建议是yield交换时的数字.这将降低启动成本,同时将迭代成本保持在O(1)(每次迭代基本上为5次操作).总成本将保持不变,但改组本身会更快.在这种情况下,因为collection.Shuffle().ToArray()它理论上会没有区别,但在上述用例中,它将加速启动.此外,这将使该算法对您只需要一些唯一项的情况很有用.例如,如果您需要从52个牌组中取出三张牌,您可以调用deck.Shuffle().Take(3)并且只会进行三次交换(尽管必须首先复制整个阵列).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
    }

    // there is one item remaining that was not returned - we return it now
    yield return elements[0]; 
}

Answer 3

从这个Skeet的引用开始:

这不是一种我喜欢的洗牌方式,主要是因为它很容易实现O(n)shuffle,这是O(n log n)的理由.问题中的代码"工作"基本上给每个元素一个随机(希望是唯一的!)数字,然后根据该数字排序元素.

我会继续解释一下希望独特的原因!

现在,从Enumerable.OrderBy:

该方法执行稳定的排序; 也就是说,如果两个元素的键相等,则保留元素的顺序

这是非常重要的!如果两个元素"接收"相同的随机数会发生什么？碰巧它们保持与阵列中的顺序相同.现在,发生这种情况的可能性有多大？很难准确计算,但生日问题正是这个问题.

现在,这是真的吗？这是真的吗？

一如既往,如有疑问,请写一些程序:http://pastebin.com/5CDnUxPG

这个小代码块使用后向完成的Fisher-Yates算法将一个3个元素的数组混洗一定次数,Fisher-Yates算法向前完成(在wiki页面中有两个伪代码算法......它们产生等价的结果,但是一个是从第一个元素到最后一个元素完成的,而另一个是从最后一个元素到第一个元素完成的,是http://blog.codinghorror.com/the-danger-of-naivete/的天真错误算法并使用.OrderBy(x => r.Next())和.OrderBy(x => r.Next(someValue)).

现在,Random.Next是

32位有符号整数,大于或等于0且小于MaxValue.

所以它相当于

OrderBy(x => r.Next(int.MaxValue))

为了测试这个问题是否存在,我们可以放大数组(非常慢)或简单地减少随机数生成器的最大值(int.MaxValue不是"特殊"数字......它只是一个非常大的数字).最后,如果算法不受稳定性的影响OrderBy,则任何值范围都应该给出相同的结果.

然后程序测试一些值,范围为1 ... 4096.从结果来看,很明显,对于低值(<128),算法非常偏向(4-8%).至少需要3个值r.Next(1024).如果你使阵列更大(4或5),那么即使r.Next(1024)还不够.我不是改组和数学方面的专家,但我认为对于数组的每个额外位长度,你需要2个额外的最大值位(因为生日悖论与sqrt(numvalues)连接),所以如果最大值是2 ^ 31,我会说你应该能够排序最多2 ^ 12/2 ^ 13位(4096-8192个元素)的数组

Answer 4

对于大多数目的来说,它可能是正常的,并且几乎总是产生一个真正的随机分布(除非Random.Next()产生两个相同的随机整数).

它的工作原理是为系列的每个元素分配一个随机整数,然后按这些整数对序列进行排序.

99.9%的应用程序完全可以接受(除非你绝对需要处理上面的边缘情况).此外,双向飞碟对其运行时的反对是有效的,因此如果你正在改变一个长列表,你可能不想使用它.

Answer 5

这个问题以前已经出现过很多次了。在 StackOverflow 上搜索 Fisher-Yates。

这是我为此算法编写的C# 代码示例。如果您愿意，可以将其参数化为其他类型。

static public class FisherYates
{
        //      Based on Java code from wikipedia:
        //      http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
        static public void Shuffle(int[] deck)
        {
                Random r = new Random();
                for (int n = deck.Length - 1; n > 0; --n)
                {
                        int k = r.Next(n+1);
                        int temp = deck[n];
                        deck[n] = deck[k];
                        deck[k] = temp;
                }
        }
}