无法排序，因为 IComparer.Compare() 方法返回不一致的结果.再

Question

最小可复制示例

在移动人们投票关闭这个问题之前，请您检查最小的可重现示例吗？

这个问题已经被问了一千次，但这一次真的没有任何意义。

我收到以下异常消息：

System.ArgumentException
HResult=0x80070057
Message=Unable to sort because the IComparer.Compare() method returns inconsistent results. Either a value does not compare equal to itself, or one value repeatedly compared to another value yields different results. IComparer: 'Minotaur.GeneticAlgorithms.LexicographicalFitnessComparer'.
Source=System.Private.CoreLib
StackTrace:
at System.Collections.Generic.IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(Object comparer)
at System.Collections.Generic.ArraySortHelper`2.Sort(TKey[] keys, TValue[] values, Int32 index, Int32 length, IComparer`1 comparer)
at System.Array.Sort[TKey,TValue](TKey[] keys, TValue[] items, IComparer`1 comparer)
at Minotaur.FitnessReportMaker.MakeReport(Array`1 fitnesses) in C:SourceminotaurMinotaurMinotaurFitnessReportMaker.cs:line 18
at Minotaur.Theseus.EvolutionEngine.Run(IEnumerable`1 initialPopulation) in C:SourceminotaurMinotaurMinotaurTheseusEvolutionEngine.cs:line 63
at Minotaur.Program.Run(ProgramSettings settings) in C:SourceminotaurMinotaurMinotaurProgram.cs:line 148
at Minotaur.ProgramSettings.OnExecute() in C:SourceminotaurMinotaurMinotaurProgramSettings.cs:line 14

当我调用此方法时：

Array.Sort(
keys: sortedFitnesses,
items: sortedFitnesses,
comparer: new LexicographicalFitnessComparer());

这是我IComparer<Fitness>实现：

namespace Minotaur.GeneticAlgorithms {
using System;
using System.Collections.Generic;
public sealed class LexicographicalFitnessComparer: IComparer<Fitness> {
public int Compare(Fitness lhs, Fitness rhs) {
var a = CompareImpl(lhs, lhs);
if (a != 0)
throw new InvalidOperationException();
var b = CompareImpl(rhs, rhs);
if (b != 0)
throw new InvalidOperationException();
var c = CompareImpl(lhs, rhs);
var d = CompareImpl(rhs, lhs);
if (c != -d)
throw new InvalidOperationException();
return c;
}
public int CompareImpl(Fitness lhs, Fitness rhs) {
if (lhs is null)
throw new ArgumentNullException(nameof(lhs));
if (rhs is null)
throw new ArgumentNullException(nameof(rhs));
if (lhs.Count != rhs.Count)
throw new ArgumentException(nameof(lhs) + " and " + nameof(rhs) + " must have the same length.");
for (int i = 0; i < lhs.Count; i++) {
if (lhs[i] < rhs[i])
return -1;
else if (lhs[i] > rhs[i])
return 1;
}
return 0;
}
}
}

如您所见，Compare方法实际上调用CompareImpl并对结果执行许多测试。 没有InvalidOperationException被抛出。所以我不知道发生了什么...

为了完整起见，这是我Fitness实现：

namespace Minotaur.GeneticAlgorithms {
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using Minotaur.ExtensionMethods.SystemArray;
using Newtonsoft.Json;
[JsonObject(MemberSerialization.OptIn)]
public sealed class Fitness: IEquatable<Fitness>, IReadOnlyList<float> {
[JsonProperty] private readonly float[] _objectives;
private readonly int _precomputedHashCode;
[JsonConstructor]
private Fitness(float[] objectives) {
for (int i = 0; i < objectives.Length; i++) {
if (float.IsNaN(objectives[i]))
throw new ArgumentException(nameof(objectives) + " can't contain NaNs.");
}
_objectives = objectives;
Count = objectives.Length;
var hash = new HashCode();
for (int i = 0; i < _objectives.Length; i++)
hash.Add(_objectives[i]);
_precomputedHashCode = hash.ToHashCode();
}
public static Fitness WrapAndCopy(float[] objectives) {
if (objectives == null)
throw new ArgumentNullException(nameof(objectives));
if (objectives.Length == 0)
throw new ArgumentException(nameof(objectives) + " can't be empty");
return new Fitness(objectives.ToArray());
}
public float this[int index] => _objectives[index];
public int Count { get; }
public override string ToString() => "[" + string.Join(", ", _objectives) + "]";
public override int GetHashCode() => _precomputedHashCode;
public override bool Equals(object obj) => Equals(obj as Fitness);
public bool Equals(Fitness other) {
if (other == null)
return false;
if (object.ReferenceEquals(this, other))
return true;
// Again, fitnesses should all have the same length
// finding one with different length indicates a critical error
if (Count != other.Count)
throw new InvalidOperationException($"Fitness should ALWAYS have the same {nameof(Count)}");
var lhs = _objectives;
var rhs = other._objectives;
for (int i = 0; i < lhs.Length; i++) {
if (lhs[i] != rhs[i])
return false;
}
return true;
}
public IEnumerator<float> GetEnumerator() => _objectives.GetGenericEnumerator();
IEnumerator IEnumerable.GetEnumerator() => _objectives.GetEnumerator();
}
}

如您所见，Fitness 是不可变的，不允许使用 NaN。 正在排序的数组是一个局部变量(因此不会被其他线程修改(，并且不包含空值。

这是一个框架错误吗？

编辑：目标框架是.NET Core 2.2。该项目是为 Windows 上的 x64 构建的。

示例输入：

{Minotaur.GeneticAlgorithms.Fitness[50]}
{[0.4032445, 144]}
{[0.3778533, 144]}
{[0.1739699, 144]}
{[0.3778533, 144]}
{[0.4032445, 144]}
{[0.1962067, 144]}
{[0.2236756, 144]}
{[0.376882, 144]}
{[0.275862, 144]}
{[0.3972802, 144]}
{[0.2236756, 144]}
{[0.1962067, 144]}
{[0.376882, 144]}
{[0.2236756, 144]}
{[0.4032445, 144]}
{[0.3684821, 144]}
{[0.3603691, 144]}
{[0.4032445, 144]}
{[0.3113146, 144]}
{[0.3176299, 144]}
{[0.2236756, 144]}
{[0.3972802, 144]}
{[0.4325995, 144]}
{[0.275862, 144]}
{[0.2972316, 144]}
{[0.376882, 144]}
{[0.3603691, 144]}
{[0.275862, 144]}
{[0.2236756, 144]}
{[0.2040549, 144]}
{[0.4032445, 144]}
{[0.3113146, 144]}
{[0.2040549, 144]}
{[0.2236756, 144]}
{[0.275862, 144]}
{[0.4032445, 144]}
{[0.3113146, 144]}
{[0.3113146, 144]}
{[0.3176299, 144]}
{[0.3118019, 144]}
{[0.3778533, 144]}
{[0.4032445, 144]}
{[0.3127732, 144]}
{[0.3176299, 144]}
{[0.3603691, 144]}
{[0.275862, 144]}
{[0.2236756, 144]}
{[0.376882, 144]}
{[0.3176299, 144]}
{[0.3603691, 144]}

Answer 1

当您不传递与keys相同的数组并items传递给Sort时，问题就消失了。

Array.Sort(sortedFitnesses, new LexicographicalFitnessComparer());

如果将相同的数组作为键和项传递，因为排序算法将尝试同时重新排列两个数组，因此会感到困惑。

例如：如果 alogorithm 决定，它必须在位置 3 和 5 交换元素，它将首先交换键数组中位置 3 和 5 的元素，然后在 items 数组中位置 3 和 5 交换元素。如果两者都是相同的数组引用，则算法完成的每次交换都会立即再次撤消。

由于只有一个数组，因此无需将其同时指定为键和项。

当首先制作数组的克隆时，排序也将起作用。

该文档解释：

键数组

中的每个键在项数组中都有一个对应的项。在排序过程中重新定位键时，项目数组中的相应项目也会类似地重新定位。因此，项目数组根据键数组中相应键的排列进行排序。

我认为Microsoft应该增强文档，并特别提到您不能对键和项目使用相同的数组。他们还可以轻松地在实现中检查这一点。

Answer 2

更新：在收到一个最小的可重现示例并运行它时，很明显出了什么问题。 比较很好，我已经删除了解释如何发现比较问题的答案。(虽然公平地说，糟糕的呼叫网站在原始帖子中;我没有仔细阅读！

真正的问题是原始海报使用的是排序版本，该版本采用要排序的键数组，并使用与键数组相同的交换对第二个数组进行排序。

那么会发生什么呢？假设两个密钥被交换，因为它们的顺序不正确。然后交换另一个数组中相应的数组元素。但它是同一个数组，所以我们只是把它们换回来，现在键的顺序错误。

那么为什么这在比较中表现出缺陷？ 因为合理的健全性检查是：

• 如果键数组中的元素顺序不正确
• 交换键数组中的元素
• 交换其他数组中的相应元素
• 检查关键元素现在是否正常

但当然不是！他们又回到了错误的顺序。

绝大多数情况下，这种异常的发生是因为比较算法本身很糟糕。

通常，键数组和其他数组甚至不是同一类型。我永远不会想到这两个数组可能是同一个数组，而且框架作者显然也没有想到，因为没有检查它。当然可以。

他们从未想过的原因可能是因为这是一件非常奇怪的事情。如果要对要排序的元素也是排序键的数组进行排序，则只需对数组进行排序。只需致电Sort(items, comparison).仅当键的排序方式与元素不同时，才使用采用键数组的版本。