问题使用IComparer进行随机播放

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

Google提出了大量有缺陷的结果，这些结果都采取以下形式：

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实例，因为我没有看到任何其他方法来执行此操作：items 必须使用其他一些真正随机的值进行比较，但是这个值必须对于给定排序操作中的项也是一致的。

我有一个开始这里，但它是匆忙发布的，是非常慢，甚至没有返回所有可能的排序（测试显示它至少消除了偏见，如果你不计算缺少的选项）。我不希望像Fisher-Yates这样的O（n）性能，但我确实想要一些合理的东西（n log n表示小n），我确实希望它显示所有可能的排序。不幸的是，这个链接是当前接受的问题的答案，因此我希望能够用更好的东西替换它。

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

10341

2018-02-17 17:38

起源

你能解释为什么这个实现有偏见或引发异常吗？（为了我自己的启发） - Brian Genisio

从我看到的，异常是NullReferenceException。偏见......不知道。 - R. Martinho Fernandes

我将添加一些代码来证明偏见。 - Joel Coehoorn

WriteList <T>上没有返回值 - Jason Punyon♦

缺少var数据行上的分号... - Jason Punyon♦

答案:

我有点惊讶这个帖子发布了多少错误的答案。只是为了提出类似于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;

2018-02-17 18:38

我想我总结了一个非常好的案例，你可能希望将正确的逻辑嵌入到IComparer中。我知道它不可能获得与Fisher-Yates相同的性能，但至少应该能够获得正确的逻辑和合理的性能。 - Joel Coehoorn

我在其他地方得到的一个建议是创建一个单独的IArranger接口来描述单个操作安排一个集合。这可以在IComparer / IComparable不能使用的地方工作，因为它在整个集合上运行，而不是单个项目。它可能看起来像这样：

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

然后我可以实现一个 Shuffle 来自IArranger接口使用适当的Fisher-Yates算法，并且还具有包装每个附加的实现 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添加对此的支持。然后你仍然可以进行简单的运行时算法交换，你有一个更好的shuffle算法实现，并且使用它的代码感觉很自然：

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

2018-02-18 14:31

我能看到你的解决方案代码吗？我似乎无法访问您的网站。干杯 - Berryl

的IComparer 要求在某一点上返回零（对于相同的T实例），就可以了数学不可能在统计上创建一个模仿Fisher-Yates Shuffle的通用IComparer。永远都会有偏见。对于真正的洗牌，你永远不想强迫它返回任何特定的价值。

2018-02-17 18:44

如何根据预先分配了随机值的隐藏字段进行排序？

2018-02-17 18:00

我希望这能为之努力任何 T：没有约束，没有投影。 - Joel Coehoorn

跟进James Curran的想法：让IComparer将“排序”值保持为列表;如果出现新值，则将其插入列表中的随机位置;按列表索引进行比较。通过将列表维护为平衡树或其他内容来进行优化。这样的IComparer的每个实例都将保持一致且随机的排序顺序，因此您可以选择让随机排序始终具有相同的随机排序或每次不同的排序。如果您希望以这种方式“随机”阅读，那么微小的修改甚至可以允许将相同的元素“排序”到不同的排序位置。

2018-02-18 00:51

这只是一种伪装Fischer-Yates shuffle的方式，基于一个时髦的比较器。 - AJMansfield

一个有趣的努力。很可能滥用/滥用IComparer。

您试图通过使用不是为此目的而构建的机制来进行随机加权排序。

为什么不实现自己的排序例程和自己的比较器？我觉得即使这样也不够。

2018-02-18 14:20

不要这样做。

到目前为止，所提出的所有算法都在输出中引入了某种偏差（有些偏差大于其他算法）。

@Princess和@Luke建议在数据旁边存储一个随机数。但是，因为这些随机数中的任何两个都可能具有与另一个相同的值，这两个项之间的排序顺序将具有确定性偏差

最糟糕的情况是，如果排序例程是“稳定的”（即被认为相等的对象总是以它们输入的相同顺序输出）。 Array.Sort不是很稳定（它在内部使用QuickSort）但是，只要两个项具有相同的值（取决于它们在输入中的位置）（特别是它们相对于QuickSort的位置），仍会出现偏差。枢）。

随着此随机数的键空间增加，碰撞的概率下降（具有良好的随机性源），但请记住，随着您排序的值的数量增加，生日悖论决定了碰撞的可能性。其中至少有一对碰撞很快就会上升。

对于整数键，键有2 ^ 32个唯一值，即使假设随机值的分布非常均匀，有75,000行，也有50％的可能性会发生冲突。维基百科。

您提出的加密哈希方法可能具有足够大的密钥空间（160）位以使冲突的可能性可以忽略不计，但是您的算法在实际执行比较之前将所有随机性分解回单个int，从而抵消了更大的键空间。

最好的方法是将一个不同的“sortOrder”值与每个数据项相关联，使用经过验证的算法对这些值进行混洗，然后按该值对结果进行排序。

如果您使用的是Array.Sort，则会出现一个带有“键”数组和“值”数组的重载。 keys数组正常排序，但每当移动keys数组中的值时，values数组中的相应条目也会移动。

就像是：


Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
 keys[i] = i;
}

Shuffle(keys);

Array.Sort(keys, data);

2018-02-18 15:46

虽然准确，但这忽略了问题的精神：1）只想根据用户选择交换IComparable实现而没有大量额外代码用于“特殊”随机情况的人。 2）一种可行的替代方案，仍然使用IComparable来处理所有“糟糕”的谷歌搜索结果。 - Joel Coehoorn

问题 使用IComparer进行随机播放

答案:

热门问题

问题使用IComparer进行随机播放