是使用Random和OrderBy一个很好的shuffle算法? [c#]


Answers

这是基于Jon Skeet的答案

在那个答案中,数组被洗牌,然后使用yield返回。 最终的结果是数组在foreach的持续时间内保存在内存中,以及迭代所需的对象,但是开销都是开始的 - 收益基本上是一个空循环。

该算法在游戏中使用了很多,前三个项目被选中,而其他的则仅在以后才需要。 我的建议是在交换数据后立即发出数字。 这将降低启动成本,同时将迭代成本保持在O(1)(每次迭代基本上有5个操作)。 总成本将保持不变,但洗牌本身会更快。 在这种情况下,这被称为collection.Shuffle().ToArray()在理论上没有什么区别,但在上述用例中它将加速启动。 此外,这将使算法对您只需要几个唯一项目的情况有用。 例如,如果您需要从52层甲板上拔出三张牌,您可以拨打deck.Shuffle().Take(3)并且只会发生三次交换(尽管必须首先复制整个数组)。

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

我已经阅读关于编码恐怖的各种洗牌算法的文章 。 我已经看到,有人做了这个,洗牌一个列表:

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

这是一个很好的洗牌算法吗? 它如何正常工作? 这是可以接受的做法吗?




从这个Skeet的报价开始:

这不是我喜欢的洗牌方法,主要是因为它是O(n log n),因为它很容易实现O(n)洗牌,没有什么好的理由。 问题“工作”中的代码通过基本给每个元素一个随机( 希望唯一的 )数字,然后根据该数字排序元素。

我会一点点解释希望独特的原因

现在,从Enumerable.OrderBy

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

这个非常重要! 如果两个元素“收到”相同的随机数会怎么样? 它发生在它们在数组中的顺序。 现在,发生这种情况的可能性是甚么? 这是很难准确计算的,但生日问题正是这个问题。

现在是真的吗 是真的吗

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

这个小块的代码使用Fisher-Yates算法反向完成了一定数量的3个元素的数组,Fisher-Yates算法完成了前进(在wiki页面中有两个伪代码算法...他们产生等价的结果,但是从第一个到最后一个元素完成,而另一个是从最后一个元素完成的), http://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))

为了测试这个问题是否存在,我们可以放大数组(一些非常慢的数据),或简单地减小随机数生成器的最大值( int.MaxValue不是一个“特殊的”数字),这只是一个非常大的数字)。 最后,如果算法没有被OrderBy的稳定性所偏好,那么任何范围的值都应该给出相同的结果。

程序然后测试一些值,范围1 ... 4096。 看看结果,很明显,对于低值(<128),算法非常有偏差(4-8%)。 使用3个值至少需要r.Next(1024) 。 如果你使数组更大(4或5),那么即使r.Next(1024)还不够。 我不是在洗牌和数学方面的专家,但是我认为,对于数组长度的每一个额外的位,你需要2个额外的最大值(因为生日悖论连接到sqrt(numvalues)),所以如果最大值是2 ^ 31,我会说你应该能够排列数组,最多为2 ^ 12/2 ^ 13位(4096-8192个元素)




稍微无关,但这里是一个有趣的方法(即使它真的超额,已经被实施了),真正的随机生成骰子卷!

骰子-O-Matic的

我在这里发布的原因是,他提出了一些有趣的观点,他的用户如何反应使用算法洗牌的想法超过实际的骰子。 当然,在现实世界中,这样一个解决方案只适用于随机性有如此大的影响,也可能是影响影响货币的极端的极端的终极。




我会说,这里的许多答案就像“这个算法通过为列表中的每个值生成一个新的随机值,然后按照这些随机值排序列表”可能是非常错误的!

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

IEnumerableSorter可能不是为每个算法步骤调用比较函数,例如quicksort,并且每次调用这两个参数的函数x => r.Next()而不缓存这些参数!

在这种情况下,您可能会真的搞乱排序算法,使其比预期的算法更加糟糕。 当然,它最终会变得稳定并返回一些东西。

我可以稍后通过将调试输出放在一个新的“下一步”功能中,看看会发生什么。 在反射器中,我无法立即找到它是如何工作的。




寻找算法? 你可以使用我的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个第一个整数的初始排序列表: { 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




启动时间运行代码,清除所有线程并缓存每个新的测试,

第一个不成功的代码。 它运行在LINQPad上。 如果你跟随测试这个代码。

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 ms

list.OrderBy(x => Guid.NewGuid())使用36.7634 ms(建议从MSDN。)

他们第二次在同一时间使用。

编辑:英特尔酷睿i7 4@2.1GHz的测试代码,Ram 8 GB DDR3 @ 1600,硬盘SATA 5200 rpm,[数据:www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;

namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("Press any key to continue . . . ");
                Console.ReadKey(true);
            }
        }

        public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;

                GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.Sleep(5000);

                st = Stopwatch.StartNew();
                #region Import Input Data
                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(temp);
                    count++;
                }
                sr.Close();
                #endregion

//              Console.WriteLine("--------------Random--------------");
//              #region Sort by Random with OrderBy(random.Next())
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with OrderBy(Guid)
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with Parallel and OrderBy(random.Next())
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with Parallel OrderBy(Guid)
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with User-Defined Shuffle Method
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion

//              #region Sort by Random with Parallel User-Defined Shuffle Method
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion

                // Result
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }

        }
    }
}

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

结论:
假设:LINQ OrderBy(r.Next())和OrderBy(Guid.NewGuid())在第一个解决方案中不比用户定义的随机播放方法差。

答:他们是矛盾的。