使用iComparer随机播放

我有点惊讶 this thread 发布了多少错误答案。为了其他人的利益,他们提出了一个类似于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(糟糕!)。无论您使用的是guid、gethashcode或任何其他随机生成的输入,上面所示的解决方案仍然是错误的。

尽管如此,Fisher Yates是排列的标准方式,因此首先没有真正的理由使用iComparer。Fisher-Yates是O(n),而使用iComparer的任何实现在时间复杂度为O(n Log n)的场景之后都使用QuickSort。没有充分的理由不使用众所周知的、高效的、标准的算法来解决这类问题。

但是,如果您确实坚持使用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);
        }
    }
}

或是和你的坏自己在一起:

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

我在别处得到的一个建议是创建一个单独的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添加对此的支持。然后您仍然可以得到简单的运行时算法交换,您可以更好地实现无序播放算法,并且使用它的代码感觉很自然:

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

排序次序 要求 在某个点(对于t的相等实例)返回零,使其 数学上的 无法创建一个通用的IComparer来模拟fisher-yates的随机播放。总会有偏见的。对于真正的随机播放,您永远不希望强制它返回任何特定的值。

如何基于一个预先分配了随机值的隐藏字段进行排序?

要跟进James Curran的想法:让iComparer将“排序”值作为列表维护;如果出现新值,请将其随机插入列表;按列表索引比较。通过将列表保持为平衡树或其他方式进行优化。这样一个IComparer的每个实例都将保持一致的随机排序顺序,因此您可以选择让您的随机排序始终保持相同的随机排序,或者每次都是不同的随机排序。如果您喜欢以这种方式读取“随机的”,微小的修改甚至允许等量元素被“排序”到不同的排序位置。

一项有趣的努力。很可能是滥用/滥用公司。

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

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

不要这样做。

到目前为止提出的所有算法都会在输出中引入某种偏差(有些偏大)。

@公主和@luke建议在数据旁边存储一个随机数。然而,由于这些随机数中的任意两个可能具有与另一个相同的值,因此这两个项目之间的排序顺序将具有确定性偏差。

最坏的情况是,如果排序例程是“稳定的”(即,被认为相等的对象总是以输入的相同顺序输出)。array.sort并不稳定(它在内部使用quicksort),但当两个项具有相同的值时,仍然存在偏差,这取决于它们在输入中的位置(特别是它们相对于quicksort的轴的位置)。

随着这个随机数的键空间的增加,碰撞的概率会降低(具有很好的随机性来源),但请记住,随着正在排序的值的数目增加,生日悖论规定,其中至少一对碰撞的可能性会很快增加。

对于整数键,该键有2^32个唯一值,即使假设随机值分布完全均匀,有75000行,也有50%的概率会发生冲突。 Wikipedia .

您提出的加密散列方法可能具有足够大的密钥空间(160)位,可以忽略碰撞的可能性,但是您的算法在实际执行比较之前将所有的随机性分解回一个整数,这会抵消较大密钥空间的好处。

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

如果您使用array.sort,则会有一个重载接受一个“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);