[c#] 是使用随机和OrderBy一个很好的洗牌算法?



Answers

这是基于Jon Skeet的answer

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

这个算法在游戏中被广泛使用,其中前三个选项被挑选出来,而其他的只在后面才需要。 我的建议是尽快交换数字。 这将减少启动成本,同时保持O(1)的迭代成本(基本上每次迭代5次操作)。 总成本将保持不变,但洗牌本身会更快。 在这种情况下,这被称为collection.Shuffle().ToArray()它理论上没有区别,但在上述使用情况下,它将加速启动。 此外,这将使该算法适用于只需要几个独特项目的情况。 例如,如果你需要从52 deck.Shuffle().Take(3)牌中抽出3张牌,你可以调用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

我在Coding Horror上看过一篇关于各种洗牌算法的文章 。 我已经看到有人在这个地方打乱了一个清单:

var r = new Random();
var shuffled = ordered.OrderBy(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毫秒

list.OrderBy(x => Guid.NewGuid())使用36.7634毫秒(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/9dw9wl259dfs04g/ResultDescription.PNG
结果统计信息: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNGhttps://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

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

答:他们是矛盾的。




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

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

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




这已经出现过很多次了。 在上搜索Fisher-Yates。

这里是我为这个算法编写的C#代码示例 。 如果您愿意,您可以在其他类型上对其进行参数化。

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



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

Dice-O-Matic

我在这里发布这个帖子的原因是,他提出了一些有趣的观点,关于他的用户如何回应使用算法来洗牌的想法,而不是真正的骰子。 当然,在现实世界中,这种解决方案只适用于频谱的真正极端,随机性具有如此大的影响,并且可能影响金钱;)。




Links