使用IComparer进行随机播放

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

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

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

但是，该实现是有偏见的，甚至会在某些情况下抛出exception。 可以使用以下代码演示偏差：

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

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

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

Answer 1

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

但是，代码偶尔会抛出exception，但并非总是如此。 这就是使调试变得有趣的原因:)如果你运行足够多次，或者在一个循环中执行排序过程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; 

Answer 2

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

 public interface IArranger { IEnumerable Arrange(IEnumerable items); } 

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

 public class ComparerArranger : IArranger { private IComparer comparer; public ComparableArranger(IComparer comparer) { this.comparer = comparer; } public IEnumerable Arrange(IEnumerable items) { return items.OrderBy(i => i, comparer); } } 

要么

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

要么

 public class ShuffleArranger : IArranger { //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 Arrange(IEnumerable 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 Arrange(this IEnumerable items, IArranger arranger) { return arranger.Arrange(items); } 

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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

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

Answer 7

不要这样做。

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

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

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

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

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

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

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

如果您使用的是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