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

Question

Minimal reproductible example

在让人们投票结束这个问题之前，请您检查一下最小的可重现示例吗？

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

我收到以下异常消息:

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。正在排序的数组是一个局部变量(因此不会被其他线程修改)并且不包含空值。

这是框架错误吗？

编辑:目标框架是 .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的元素，它会先交换keys数组中位置3和5的元素，然后交换items数组中位置3和5的元素。如果两者都是相同的数组引用，则算法完成的每次交换都会立即再次撤消。

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

排序也适用于先克隆数组。

文档解释:

Each key in the keys Array has a corresponding item in the items Array. When a key is repositioned during the sorting, the corresponding item in the items Array is similarly repositioned. Therefore, the items Array is sorted according to the arrangement of the corresponding keys in the keys Array.

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