当前位置:  开发笔记 > 编程语言 > 正文

使用IComparer进行随机播放

如何解决《使用IComparer进行随机播放》经验,为你挑选了1个好方法。

首先,我确实知道Fisher-Yates shuffle.但为了论证,我想允许用户从下拉列表中选择一个排序选项.该列表将包括"随机"选项.根据他们的选择结果,我只想在IComparer实例中替换我的排序.IComparer会是什么样子?

谷歌提出了大量有缺陷的结果,所有结果都采取以下形式:

public class NaiveRandomizer : IComparer
{
    private static Random rand = new Random();

    public int Compare(T x, T y)
    {
        return (x.Equals(y))?0:rand.Next(-1, 2);
    }
}

但是,该实现是有偏见的,甚至会在某些情况下抛出异常.可以使用以下代码演示偏差:

void Test()
{
    Console.WriteLine("NaiveRandomizer Test:");
    var data = new List() {1,2,3};
    var sortCounts = new Dictionary(6);
    var randomly = new NaiveRandomizer();

    for (int i=0;i<10000;i++)
    {   //always start with same list, in _the same order_.
        var dataCopy = new List(data); 
        dataCopy.Sort(randomly);

        var key = WriteList(dataCopy);
        if (sortCounts.ContainsKey(key))
            sortCounts[key]++;
        else
            sortCounts.Add(key, 1);
    }

    foreach (KeyValuePair item in sortCounts)
        Console.WriteLine(item.Key + "\t" + item.Value);
}

string WriteList(List list)
{
   string delim = "";
   string result = "";
   foreach(T item in list)
   {
       result += delim + item.ToString();
       delim = ", ";
   }
   return result;
}

那你怎么能实现IComparer解决这些问题的随机性呢?允许每次调用都要.Sort()使用单独的IComparer实例,因为我没有看到任何其他方法来执行此操作:必须使用其他一些真正随机的值来比较项目,但该值对于项目也必须是一致的在给定的排序操作中.

我开始在这里,但它被张贴在仓促,是极其缓慢的,甚至不返回所有可能的排序(测试表明,它确实至少消除偏见,如果你不指望缺少的选项).我不希望O(n)表现像Fisher-Yates那样,但我确实想要一些合理的东西(n log n表示小n),我确实希望它显示所有可能的排序.不幸的是,这个链接是当前接受的答案,所以我希望能够用更好的东西替换它.

如果不出意外的话,我希望这可以成为所有谷歌查询寻找IComparable解决方案的磁铁 - 他们最终会在这里而不是其他地方告诉他们使用不正确的版本.



1> Juliet..:

我对这个帖子有点惊讶,发布了多少错误的答案.只是为了提出类似于OP发布的解决方案的其他人,以下代码看起来是正确的:

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

但是,代码偶尔会抛出异常,但并非总是如此.这就是让调试变得有趣的原因:)如果你运行它足够多次,或者在一个循环中执行排序过程50次左右,你会得到一个错误说明:

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x's type: 'Int32' The IComparer: ''.

换句话说,快速排序将一些数字x与自身进行比较并获得非零结果.代码的明显解决方案是写:

Array.Sort(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

但即使这样也行不通,因为有时.NET会将3个数字相互比较,从而返回不一致的结果,例如A> B,B> C和C> A(oops!).无论您使用Guid,GetHashCode还是任何其他随机生成的输入,上面显示的解决方案仍然是错误的.


话虽如此,Fisher-Yates是改组数组的标准方法,所以没有真正的理由首先使用IComparer.Fisher-Yates是O(n),而使用IComparer的任何实现都使用具有时间复杂度O(n log n)的场景后面的快速排序.没有充分的理由不使用众所周知的,有效的标准算法来解决这类问题.

但是,如果您真的坚持使用IComparer和rand,那么排序之前应用随机数据.这需要将数据投影到另一个对象上,这样您就不会丢失随机数据:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair[] nums = new Pair[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair(i, r.NextDouble());
            }

            Array.Sort>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

或者用自己糟糕的自己获得LINQy:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;

推荐阅读
贾志军
这个屌丝很懒,什么也没留下!
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有