使用 Random 和 OrderBy 是否是一个好的 shuffle 算法? [英] Is using Random and OrderBy a good shuffle algorithm?

问题描述

我已经阅读了 一篇文章，关于各种 shuffle 算法在 编码恐怖.我已经看到有人在某处这样做来洗牌:

I have read an article about various shuffle algorithms over at Coding Horror. I have seen that somewhere people have done this to shuffle a list:

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

这是一个好的洗牌算法吗?它是如何工作的?这是一种可接受的方式吗?

Is this a good shuffle algorithm? How does it work exactly? Is it an acceptable way of doing this?

推荐答案

这不是我喜欢的洗牌方式，主要是因为它是 O(n log n) 没有充分的理由，当它很容易实现 O(n) 洗牌.问题有效"中的代码基本上是给每个元素一个随机的(希望是唯一的！)数字，然后根据该数字对元素进行排序.

It's not a way of shuffling that I like, mostly on the grounds that it's O(n log n) for no good reason when it's easy to implement an O(n) shuffle. The code in the question "works" by basically giving a random (hopefully unique!) number to each element, then ordering the elements according to that number.

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

I prefer Durstenfeld's variant of the Fisher-Yates shuffle which swaps elements.

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

Implementing a simple Shuffle extension method would basically consist of calling ToList or ToArray on the input then using an existing implementation of Fisher-Yates. (Pass in the Random as a parameter to make life generally nicer.) There are plenty of implementations around... I've probably got one in an answer somewhere.

这种扩展方法的好处在于，它会让读者非常清楚你实际上想要做什么.

The nice thing about such an extension method is that it would then be very clear to the reader what you're actually trying to do.

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

Here's a simple implementation (no error checking!):

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

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

Comments on performance below reminded me that we can actually return the elements as we shuffle them:

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

这现在只会做它需要做的工作.

This will now only do as much work as it needs to.

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

Note that in both cases, you need to be careful about the instance of Random you use as:

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

• Creating two instances of Random at roughly the same time will yield the same sequence of random numbers (when used in the same way)
• Random isn't thread-safe.

我有 一篇关于 Random 的文章更详细地了解这些问题并提供解决方案.

I have an article on Random which goes into more detail on these issues and provides solutions.

这篇关于使用 Random 和 OrderBy 是否是一个好的 shuffle 算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！