是使用随机和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())不会比用户定义的混洗方法差。

    答:他们是矛盾的。