使用随机排序依据一个很好的洗牌算法？ [英] Is using Random and OrderBy a good shuffle algorithm?

问题描述

我已经阅读有关各种洗牌算法的文章在上的Coding恐怖。我看到某处的人已经这样做了重新洗牌的列表：

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）的洗牌。在code。在这个问题：作品，由基本上每个元素赋予一个随机的（唯一的希望！）号码，然后根据这个数字排序的元素。

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.

我preFER的费雪耶茨洗牌其中交换的元素。

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

实现一个简单的随机扩展方法将基本上包括呼叫了ToList 或的ToArray 上，然后使用费雪耶茨的现有实现输入。 （传中随机作为参数，使生活一般更好。）有很多实现的身边......我可能已经得到了一个在答案的地方。

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.

请注意，在这两种情况下，你必须要小心随机您使用的实例：

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

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

• 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.

我有对随机文章 肚里就这些问题，更多的细节和提供解决方案。

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

这篇关于使用随机排序依据一个很好的洗牌算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！