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

问题描述 投票：0回答：3

最小可重现示例

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

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

我收到以下异常消息：

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]}
c# sorting
3个回答
9
投票

当您不将与 

keys
和 
items
相同的数组传递给 
Sort
时，问题就会消失。

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

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

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

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

首先克隆数组时，排序也可以工作。

文档说明：

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

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

4
投票

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

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

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

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

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

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

绝大多数时候出现这种异常是因为比较算法本身不好。

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

他们从未想到这一点的原因可能是因为这是一件非常奇怪的事情。如果要对一个数组进行排序，其中被排序的元素也是排序键，则只需对数组进行排序即可。只需拨打

Sort(items, comparison)
即可。如果键的排序方式与元素不同，则仅使用采用键数组的版本。

0
投票

我通过设置控制面板\时钟和区域\区域 - >其他设置 - >标准数字（它是空的）来修复这种情况 screen 1 screen 2

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.