是使用随机和OrderBy一个很好的洗牌algorithm?

我在Coding Horror上看了一篇关于各种shufflealgorithm的文章 。 我看到有人在这个地方打乱了一个清单:

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

这是一个很好的洗牌algorithm吗? 它是如何工作的? 这是一个可以接受的方式吗?

这不是我喜欢的洗牌方式,主要是因为它很容易实现O(n)洗牌,所以没有理由就是O(n log n)。 基本上给每个元素一个随机的(希望是唯一的!)数字,然后根据这个数字对元素进行sorting,问题中的代码“起作用”。

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

实现一个简单的Shuffle扩展方法基本上包括在input上调用ToListToArray ,然后使用现有的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; } } 

编辑:下面的performance的评论提醒我,我们可以实际上返回的元素,我们洗牌:

 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使用的实例:

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

我有一篇关于Random的文章,详细介绍这些问题并提供解决scheme。

这是基于Jon Skeet的回答 。

在这个答案中,数组被洗牌,然后使用yield返回。 最终的结果是数组在foreach期间保存在内存中,以及迭代所需的对象,但是开始的代价是全部 – 成本基本上是一个空循环。

这个algorithm在游戏中被使用了很多,前三个选项被选中,而其他的则只有后来才需要。 我的build议是尽快交换数字。 这将减less启动成本,同时保持O(1)的迭代成本(基本上每次迭代5次操作)。 总成本将保持不变,但洗牌本身会更快。 在这种情况下,这被称为collection.Shuffle().ToArray()它理论上将没有任何区别,但在上述使用情况下,它将加快启动。 此外,这将使algorithm有用的情况下,你只需要一些独特的项目。 例如,如果你需要从52 deck.Shuffle().Take(3)牌中抽出3张牌,你可以调用deck.Shuffle().Take(3)只有三次交换(尽pipe整个数组必须先被复制)。

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

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

它通过为系列的每个元素分配一个随机整数,然后按这些整数对序列进行sorting来工作。

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

从这个Skeet的报价开始:

这不是我喜欢的洗牌方式,主要是因为它很容易实现O(n)洗牌,所以没有理由就是O(n log n)。 基本上给每个元素一个随机的( 希望是唯一的! )数字,然后根据这个数字对元素进行sorting,问题中的代码“起作用”。

我会稍微解释一下希望独特的原因

现在,从Enumerable.OrderBy :

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

这个非常重要! 如果两个元素“接收”相同的随机数,会发生什么? 碰巧它们仍然与数组中的顺序保持一致。 现在有什么可能发生? 确切地计算是困难的,但生日问题正是这个问题。

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

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

这个小块代码使用向后完成的Fisher-Yatesalgorithm将3个元素的数组重新sorting,向前完成Fisher-Yatesalgorithm(在wiki页面中有两个伪代码algorithm…它们产生等效结果,但是一个是从第一个到最后一个元素,而另一个是从最后到第一个元素完成的),天真的错误algorithmhttp://blog.codinghorror.com/the-danger-of-naivete/和使用.OrderBy(x => r.Next()).OrderBy(x => r.Next(someValue))

现在, Random.Next是

大于或等于0且小于MaxValue的32位有符号整数。

所以它相当于

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

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

程序然后testing一些值,范围在1 … 4096。 看看结果,很明显,对于低值(<128),algorithm是非常有偏见的(4-8%)。 有了3个值,你至less需要r.Next(1024) 。 如果你把数组r.Next(1024) 4或5),那么甚至r.Next(1024)是不够的。 我不是洗牌和math方面的专家,但是我认为对于数组的每个额外的位,你需要额外的2位的最大值(因为生日悖论连接到sqrt(numvalues)),所以如果最大值是2 ^ 31,我会说你应该能够排列高达2 ^ 12/2 ^ 13位(4096-8192个元素)

看起来像一个很好的洗牌algorithm,如果你不是太担心的performance。 我指出的唯一问题是它的行为是不可控的,所以你可能很难testing它。

一个可能的select是将一个种子作为parameter passing给随机数发生器(或随机发生器作为参数),这样就可以更容易地进行控制和testing。

稍微不相关的,但这是一个有趣的方法(即使它真的是过度,真的已经实施)真正的随机生成骰子卷!

骰子-O-Matic的

我在这里发表的原因是他提出了一些有趣的观点,关于他的用户如何反应使用algorithm来洗牌的想法,而不是真正的骰子。 当然,在现实世界中,这样的解决scheme只是针对频谱的真正极端,随机性有如此大的影响,也许影响到了金钱)。

这已经出现了很多次。 在StackOverflow上searchFisher-Yates。

这里是我为这个algorithm编写的C#代码示例 。 如果您愿意,您可以在其他types的参数化。

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

我会说在这里有很多答案,比如“这个algorithm通过为列表中的每个值生成一个新的随机值,然后按这些随机值对列表进行sorting”可能是非常错误的!

我认为这不会为源集合的每个元素分配一个随机值。 相反,可能会有一个像Quicksort一样运行的sortingalgorithm,它可能会调用一个比较函数大约n个n次。 algortihm真的希望这个比较函数是稳定的,总是返回相同的结果!

难道IEnumerableSorter不是为每个快速sorting的algorithm步骤调用一个比较函数, x => r.Next()每次都调用函数x => r.Next()x => r.Next()这两个参数!

在这种情况下,你可能真的搞乱了sortingalgorithm,使得它比预期的algorithm更糟糕。 当然,它最终会变得稳定,并返回一些东西。

我稍后可以通过在新的“Next”函数中joindebugging输出来检查它,看看会发生什么。 在Reflector中,我无法立即知道它是如何工作的。

我发现Jon Skeet的答案是完全令人满意的,但是我的客户的机器人扫描器会报告Random任何实例作为安全缺陷。 所以我换了System.Security.Cryptography.RNGCryptoServiceProvider 。 作为奖励,它修复了所提到的线程安全问题。 另一方面, RNGCryptoServiceProvider测量速度比使用Random慢300 RNGCryptoServiceProvider

用法:

 using (var rng = new RNGCryptoServiceProvider()) { var data = new byte[4]; yourCollection = yourCollection.Shuffle(rng, data); } 

方法:

 /// <summary> /// Shuffles the elements of a sequence randomly. /// </summary> /// <param name="source">A sequence of values to shuffle.</param> /// <param name="rng">An instance of a random number generator.</param> /// <param name="data">A placeholder to generate random bytes into.</param> /// <returns>A sequence whose elements are shuffled randomly.</returns> public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data) { var elements = source.ToArray(); for (int i = elements.Length - 1; i >= 0; i--) { rng.GetBytes(data); var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1); yield return elements[swapIndex]; elements[swapIndex] = elements[i]; } } 

寻找一个algorithm? 你可以使用我的ShuffleList类:

 class ShuffleList<T> : List<T> { public void Shuffle() { Random random = new Random(); for (int count = Count; count > 0; count--) { int i = random.Next(count); Add(this[i]); RemoveAt(i); } } } 

然后,像这样使用它:

 ShuffleList<int> list = new ShuffleList<int>(); // Add elements to your list. list.Shuffle(); 

它是如何工作的?

我们来看一下5个第一个整数的初始sorting列表: { 0, 1, 2, 3, 4 }

该方法首先计算元素的数量并将其称为count 。 然后,在每一步count递减的情况下,它将取一个介于0count之间的随机数,并将其移动到列表的末尾。

在下面的分步示例中,可以移动的项目是斜体 ,所选项目是粗体

0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2

该algorithm通过为列表中的每个值生成一个新的随机值,然后通过这些随机值对列表进行sorting。 把它看作是在内存表中添加一个新列,然后用GUID填充,然后按该列进行sorting。 看起来像对我来说是一个有效的方式(特别是与lambda糖!)

启动时运行代码清除所有线程和caching每个新的testing,

首先不成功的代码。 它在LINQPad上运行。 如果你按照testing这个代码。

 Stopwatch st = new Stopwatch(); st.Start(); var r = new Random(); List<string[]> list = new List<string[]>(); list.Add(new String[] {"1","X"}); list.Add(new String[] {"2","A"}); list.Add(new String[] {"3","B"}); list.Add(new String[] {"4","C"}); list.Add(new String[] {"5","D"}); list.Add(new String[] {"6","E"}); //list.OrderBy (l => r.Next()).Dump(); list.OrderBy (l => Guid.NewGuid()).Dump(); st.Stop(); Console.WriteLine(st.Elapsed.TotalMilliseconds); 

list.OrderBy(x => r.Next())使用38.6528毫秒

list.OrderBy(x => Guid.NewGuid())使用36.7634毫秒(从MSDN推荐)。

在第二次之后他们两个在同一时间使用。

编辑:testing代码在英特尔酷睿i7 4@2.1GHz,Ram 8 GB DDR3 @ 1600,硬盘SATA 5200转每分钟[数据:www.dropbox.com/s/pbtmh5s9lw285kp/data]

 使用系统;
使用System.Runtime;
使用System.Diagnostics;
使用System.IO;
使用System.Collections.Generic;
使用System.Collections;
使用System.Linq;
使用System.Threading;

命名空间algorithm
 {
    上课程序
     {
         public static void Main(string [] args)
         {
            尝试{
                 int i = 0;
                 int limit = 10;
                 var result = GetTestRandomSort(limit);
                 foreach(结果中的var元素){
                     Console.WriteLine();
                     Console.WriteLine(“time {0}:{1} ms”,++ i,element);
                 }
             catch(Exception e){
                 Console.WriteLine(e.Message);
            最后{
                 Console.Write(“按任意键继续...”);
                 Console.ReadKey(真);
             }
         }

        公共静态IEnumerable <double> GetTestRandomSort(int限制)
         {
             for(int i = 0; i <5; i ++){
                 string path = null,temp = null;
                秒表st = null;
                 StreamReader sr = null;
                诠释?  count = null;
                 List <string> list = null;
                随机r = null;

                所以GC.Collect();
                 GC.WaitForPendingFinalizers();
                 Thread.sleep代码(5000);

                 st = Stopwatch.StartNew();
                 #region导入input数据
                 path = Environment.CurrentDirectory +“\\ data”;
                 list = new List <string>();
                 sr = new StreamReader(path);
                 count = 0;
                 while(count <limit &&(temp = sr.ReadLine())!= null){
 // Console.WriteLine(temp);
                     list.Add(温度);
                    计数++;
                 }
                 sr.Close();
                 #endregion

 // Console.WriteLine(“-------------- Random --------------”);
 // #region用OrderBysorting(random.Next())
 // r = new Random();
 // list = list.OrderBy(l => r.Next())。ToList();
 // #endregion

 // #region按OrderBysorting(Guid)
 // list = list.OrderBy(l => Guid.NewGuid())。ToList();
 // #endregion

 // #region按Random和OrderBysorting(random.Next())
 // r = new Random();
 // list = list.AsParallel()。OrderBy(l => r.Next())。ToList();
 // #endregion

 //#地区sorting随机并行OrderBy(Guid)
 // list = list.AsParallel()。OrderBy(l => Guid.NewGuid())。ToList();
 // #endregion

 //#地区按用户定义的随机播放方式随机sorting
 // r = new Random();
 // list = list.Shuffle(r).ToList();
 // #endregion

 //#地区sorting随机与并行用户定义随机播放方法
 // r = new Random();
 // list = list.AsParallel()。Shuffle(r).ToList();
 // #endregion

                 //结果
 //              
                 st.Stop();
                产量回报st.Elapsed.TotalMilliseconds;
                 foreach(var元素在列表中){
                 Console.WriteLine(元件);
             }
             }

         }
     }
 }

结果说明: https : //www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
结果统计: https : //www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

结论:
假设:在第一个解决scheme中,LINQ OrderBy(r.Next())和OrderBy(Guid.NewGuid())不会比用户定义的混洗方法差。

答:他们是矛盾的。