代码之家 › 专栏 › 技术社区 › Nap

为什么在排序中使用Random导致[无法排序IComparer.Compare错误]

random sorting list linq c#

Nap · 技术社区 · 14 年前

我试着用两种代码洗牌字节列表:

myList.Sort((a, b) => this._Rnd.Next(-1, 1));

或

myList.Sort(delegate(byte b1, byte b2)
{
    return this._Rnd.Next(-1, 1);
});

他们抛出了以下错误:

无法排序,因为IComparer.Compare()方法返回的结果不一致。一个值与自身不相等,或者一个值与另一个值重复比较会产生不同的结果。x: “{0}”,x的类型:“{1}”,IComparer:“{2}”。

我试着用LINQ函数来代替它,结果它成功了。

var myNewList = myList.OrderBy(s => Guid.NewGuid());
var myNewList = myList.OrderBy(s => this._Rnd.NextDouble());

我确实读到这些方法比FisherYates shuffle只提供O(n)运行时要慢。但只是想知道如何使用排序函数和随机数。

3 回复 | 直到 14 年前

winwaed 14 年前

因为正如错误所说,随机性是不一致的。必须有一个比较器,当给定相同的参数时,它总是返回相同的结果。否则排序将不一致。

Knuth有一个随机排序算法,它像插入排序一样工作,但是在现有数组中用随机选择的位置交换值。

Eric Lippert 14 年前

不仅要求比较关系 ,还要求 . 例如,你不能说“袜子比鞋子小,衬衫不比裤子小,也不比裤子大”之类的话,把它输入排序算法,然后期望得到一个把另一端弄清楚。比较排序称为比较排序 因为它们需要一个格式良好的比较关系 . 特别是,如果比较关系不一致、传递性和总排序,quicksort可以永远运行或给出无意义的结果。

如果你想要的是洗牌,那么就实现费希尔-耶茨洗牌。(正确地执行;尽管算法很简单,但几乎总是实现错误。)如果您想要的是拓扑排序,则实现拓扑排序。使用正确的工具来完成工作。

Joel Coehoorn 8 年前

排序算法通常通过定义比较函数来工作。算法将重复比较要排序的序列中的两个项,如果它们的当前顺序与所需顺序不匹配,则交换它们。算法之间的差异主要是在给定的环境下找到最有效的方法来进行所有的比较。

在进行所有这些比较的过程中,一个序列中相同的两个元素通常需要进行多次比较!使用非数字数据来简化此过程,假设您有值为“Red”和“Apple”的项。随机比较器在第一次比较中选择“Apple”作为较大的项。稍后,如果随机比较器选择“Red”作为更大的项,并且这种来回继续,那么您可能会在以下情况下结束: .

大多数情况下什么也没发生。但有时你不会…。Net很擅长的不仅仅是长跑和防范这种情况,而是它(和 应该! )当这些守卫检测到不一致的顺序时抛出异常。

当然了对的

值得一提的是,有时一个简单的费舍尔·耶茨是不合适的。一个例子是需要随机化一个未知长度的序列。。。假设您希望随机重新排列从网络流接收的数据,而不知道流中有多少数据,并尽快将该数据馈送到其他地方的工作线程。

在这种情况下,你不能完全随机化这些数据。在不知道流的长度的情况下,您没有足够的信息来正确地执行shuffle,即使您知道,您可能会发现流的长度太长,以至于无法将其全部保存在RAM甚至磁盘上。或者您可能会发现流在数小时内无法完成,但您的工作线程需要更快地运行。在这种情况下,您可能会接受(并且理解这是“解决”很重要)一种算法,该算法加载足够长的缓冲区,随机化缓冲区,将大约一半的缓冲区馈送给工作线程,然后重新填充缓冲区的空部分以重复该过程。即使在这里,您也可能使用Knuth Fisher-Yates作为随机缓冲区的步骤。