由于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:\Source\minotaur\Minotaur\Minotaur\FitnessReportMaker.cs:line 18
   at Minotaur.Theseus.EvolutionEngine.Run(IEnumerable`1 initialPopulation) in C:\Source\minotaur\Minotaur\Minotaur\Theseus\EvolutionEngine.cs:line 63
   at Minotaur.Program.Run(ProgramSettings settings) in C:\Source\minotaur\Minotaur\Minotaur\Program.cs:line 148
   at Minotaur.ProgramSettings.OnExecute() in C:\Source\minotaur\Minotaur\Minotaur\ProgramSettings.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。要排序的数组是一个局部变量（因此不会被其他线程修改），并且不包含任何null。

这是框架错误吗？

编辑：目标框架是.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());

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

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

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

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

该文档说明：

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

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

Answer 2

更新：收到一个最小的可重现示例并运行它后，很明显出了什么问题。比较很好，我删除了解释如何通过比较发现问题的答案。（尽管公平地说，错误的调用站点在原始帖子中；我没有仔细阅读它！）

真正的问题是，原始海报使用的 sort 版本需要一个要排序的键数组和一个使用与键数组相同的交换来排序的第二个数组。

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

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

• 如果键数组中的元素无序
• 交换键数组中的元素
• 交换另一个数组中的相应元素
• 检查关键要素现在是否按顺序排列

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

绝大多数情况下发生这种异常是因为比较算法本身不好。

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

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