我在Coding Horror上阅读了一篇有关各种随机播放算法的文章。我已经看到有人在这样做以随机排列列表:
var r = new Random(); var shuffled = ordered.OrderBy(x => r.Next());
这是一个很好的随机播放算法吗?究竟如何运作?这是可以接受的方式吗?
这不是我喜欢的一种改组方式,主要是因为它很容易实现O(n)改组,而没有充分的理由是O(n log n)。问题“工作”中的代码基本上是为每个元素赋予一个随机(希望是唯一的!)数字,然后根据该数字对元素进行排序。
我更喜欢Durstenfield的Fisher-Yates shuffle的变体,它可以交换元素。
实现一个简单的Shuffle扩展方法基本上将包括调用ToList或ToArray在输入上,然后使用现有的Fisher- Yates实现。(Random将参数作为参数传递,以使生活更美好。)周围有很多实现方式……我可能在某个地方给出了答案。
Shuffle
ToList
ToArray
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其中将详细介绍这些问题并提供解决方案。