使用 Random 和 OrderBy 是一种很好的随机播放算法吗? [英] Is using Random and OrderBy a good shuffle algorithm?

问题描述

我已阅读 一篇文章，关于各种随机播放算法的内容位于 编码恐怖.我看到有人在某个地方这样做来洗牌:

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) 没有充分的理由(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 是一种很好的随机播放算法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！