随机播放使用的IComparer [英] Shuffle using IComparer
问题描述
首先，我不知道费雪耶茨洗牌。但让说，为了讨论各种情形，我想允许用户选择从下拉列表中选择一个排序选项。这份名单将包括一个随机选项。根据他们选择的结果我只是想在IComparer的实例来代替我的排序。将在的IComparer是什么样子
First of all, I do know about the Fisher-Yates shuffle. But lets say for arguments sake that I want to allow the user to pick a sort option from a Dropdown list. This list would include a "Random" option. Based on the result of their selection I just want to substitute in an IComparer instance for my sort. What would the IComparer look like?
谷歌带来了有缺陷的结果过多，所有采取这种形式：
Google brings up a plethora of flawed results that all take this form:
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);
}
}
然而，实施有偏见，甚至会引发例外在某些情况下。偏置可以用下面的代码来说明：
However, that implementation is biased and will even throw an exception in some circumstances. The bias can be demonstrated with the following code:
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;
}
所以， ; 就解决这些问题？它允许要求每个调用的.sort（）使用单独的IComparer实例，因为我没有看到任何其他的方式做到这一点：项目的必须的使用一些其他的，真正的随机值进行比较，但该值的必须的也是一个给定的排序操作中的项是一致的。
So how could you implement a random IComparer<T> that solved those issues? It is allowed to require each call to .Sort() to use a separate IComparer instance, as I don't see any other way to do this: items must be compared using some other, truly random value, but that value must also be consistent for an item within a given sort operation.
我有一个开始的此处，但它被张贴在仓促，是的非常的慢，甚至不返回所有可能的各种（测试表明，它并至少消除偏见，如果你不不会数数丢失的选项）。我不希望像费雪耶茨O（n）的表现，但我想要的东西合理的（N日志N一小十岁上下的N），而且我也希望它显示所有可能的排序。不幸的是，该链接是当前公认的答案为它的问题，所以我希望能够更好的东西一点点来取代它。
I have a start here, but it was posted in haste, is extremely slow, and doesn't even return all possible sorts (testing shows that it does at least eliminate bias, if you don't count the missing options). I don't expect O(n) performance like Fisher-Yates, but I do want something reasonable (n log n for a small-ish n), and I do expect it to show all possible sorts. Unfortunately, that link is the current accepted answer for it's question and so I'm hoping to be able to replace it with something a little better.
如果不出意外，我希望这是所有寻找一个解决方案为IComparable的，他们将在这里结束，而不是别的地方，告诉他们使用的版本不正确的谷歌查询的磁铁。
If nothing else, I want this to be a magnet for all those google queries looking for an IComparable solution- that they'll end up here instead of somewhere else telling them to use the incorrect version.
推荐答案
一个建议我在其他地方是创建一个描述单个操作的安排集合的独立IArranger接口。这可以在哪里工作的IComparer / IComparable的总不能因为它的运作，而不是单个项目的整个集合。它看起来是这样的：
One suggestion I got elsewhere was to create a separate IArranger interface that describes a single operation to Arrange a collection. This can work where IComparer/IComparable cannot because it operates on an entire collection, instead of individual items. It might look something like this:
public interface IArranger<T>
{
IEnumerable<T> Arrange(IEnumerable<T> items);
}
然后我可以实现一个随机 IEnumerable.Sort（）/ IComparable的/的IComparer 品种实现$ C>从IArranger接口。这可能是这个样子：
Then I could implement a Shuffle from the IArranger interface using a proper Fisher-Yates algorithm, and also have implementations that wrap each additional IEnumerable.Sort()/IComparable/IComparer varieties that I care about. That might look something like this:
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的任何。然后，你仍然可以得到简单的运行时间算法交换，你有一个更好的实施洗牌算法，并使用它感觉自然的代码：
For a final step, I add support for this to any IEnumerable via an extension method. Then you still get the simple run-time algorithm swapping, you have a better implementation of the shuffle algorithm, and the code to use it feels natural:
public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
return arranger.Arrange(items);
}
这篇关于随机播放使用的IComparer的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
