使用IComparer进行随机播放

Question

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

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

public class NaiveRandomizer<T> : IComparer<T>
{
    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<int>() {1,2,3};
    var sortCounts = new Dictionary<string, int>(6);
    var randomly = new NaiveRandomizer<int>();

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

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

    foreach (KeyValuePair<string, int> item in sortCounts)
        Console.WriteLine(item.Key + "\t" + item.Value);
}

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

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

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

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

Answer 1

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

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

Random r = new Random();
Array.Sort<int>(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<int>(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<T, U>
    {
        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<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(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;

Answer 2

我在其他地方得到的一个建议是创建一个单独的 IArranger 接口，它描述了排列集合的单个操作。这可以在 IComparer/IComparable 无法工作的情况下工作，因为它对整个集合而不是单个项目进行操作。它可能看起来像这样：

public interface IArranger<T>
{
    IEnumerable<T> Arrange(IEnumerable<T> items);
}

然后，我可以Shuffle使用适当的 Fisher-Yates 算法实现 IArranger 接口，并且还可以实现包装IEnumerable.Sort()/IComparable/IComparer我关心的每个其他品种。这可能看起来像这样：

public class ComparerArranger<T> : IArranger<T>
{
    private IComparer<T> comparer;

    public ComparableArranger(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i, comparer);
    }
}

或者

//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T> 
{
    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i);
    }
}

或者

public class ShuffleArranger<T> : IArranger<T>
{
    //naive implementation for demonstration
    // if I ever develop this more completely I would try to
    // avoid needing to call .ToArray() in here
    // and use a better prng
    private Random r = new Random();

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
        var values = items.ToArray();

        //valid Fisher-Yates shuffle on the values array
        for (int i = values.Length; i > 1; i--)
        {
            int j = r.Next(i);
            T tmp = values[j];
            values[j] = values[i - 1];
            values[i - 1] = tmp;
        }
        foreach (var item in values) yield return item;
    }
}

最后一步，我通过扩展方法向任何 IEnumerable 添加对此的支持。然后，您仍然可以获得简单的运行时算法交换，您可以更好地实现洗牌算法，并且使用它的代码感觉很自然：

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
    return arranger.Arrange(items);
}