Java 集合排序：DEBUG/VERBOSE "Comparison method violates its general contract:" 错误的根本原因

Question

肯定有很多 Collections.sort 无法通过自我调查或调试轻松解决的问题示例。有没有办法调试和详细说明，哪 3 个对象/比较导致以下错误？即MyObject1、MyObject2和MyObject3。我们如何在没有 google/Whosebug 帮助的情况下调试它们？

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:895)
        at java.util.TimSort.mergeAt(TimSort.java:512)
        at java.util.TimSort.mergeCollapse(TimSort.java:435)
        at java.util.TimSort.sort(TimSort.java:241)
        at java.util.Arrays.sort(Arrays.java:1512)
        at java.util.ArrayList.sort(ArrayList.java:1454)
        at java.util.Collections.sort(Collections.java:175)

这是我的代码命中这个

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        // Actual energy comparison :-
        // THE higher the energy, the earlier in the list
        float delta = m1.getTotalEnergy() - m2.getTotalEnergy();

        if (delta > 0) {
            return 1;
        } else if (delta < 0) {
            return -1;
        } else {
            return 0;
        }
    }
});

同样，我想查看所有涉及此违规行为的对象。 MyObject1,2 和 3。我不是在问上面的代码有什么问题。我已经问过并得到了答复在这里，我想问我自己如何 DEBUG/MONITOR 这些错误。

Answer 1

您可以使用 IDE 的调试器并在 java.util.TimSort 上设置异常检测点。

Answer 2

看来你的排序不严格。您的 getTotalEnergy() 是否随时间变化，即是否随时间给出不同的结果？

在我看来，你的比较看起来不错，但你可以试试

Collections.sort(sorted, new Comparator<MyObject>() {
    @Override
    public int compare(MyObject m1, MyObject m2) {
        return (int) Math.sign(m1.getTotalEnergy() - m2.getTotalEnergy());
    }
});

我是不是漏掉了什么，或者你能简单地调试你与

的比较吗

System.out.println("comparing: " + m1.getTotalEnergy() + " <-> " + m2.getTotalEnergy());

打印的最后一行应该是您的无效数据。

Answer 3

异常是非常自我描述的，当提供 Comparator 不可传递时会发生违反合同的情况。为什么你的 Comparator 不是可传递的？因为您提供了 not accurate subtraction 个浮点值。 Java 和其他编程语言是正常的。换句话说，您假设 0.1 - 0.1 会产生 0，但它不会。

您的减法结果似乎非常冗长，无法严格与 0 进行比较。例如，如果您尝试对具有相同 totalEnergy 值的 2 个对象的 Collection 进行排序，前提是对于 object1.compareTo(object2) 和反之亦然，比较方法将 return 值大于零。

我可以建议您使用 BigDecimal 而不是 float，它提供更准确的计算。

@Override
public int compare(MyObject m1, MyObject m2) {
    BigDecimal bd1 = BigDecimal.valueOf(m1.getTotalEnergy());
    BigDecimal bd2 = BigDecimal.valueOf(m2.getTotalEnergy());
    return bd1.compareTo(bd2);
}

另请参阅：

float number is not the expected number after subtraction
Why does this subtraction not equal zero?
What's wrong with using == to compare floats in Java?

调试过程：

深入 sources of JDK。如果你看一下 java.util.TimSort.mergeHi(int base1, int len1, int base2, int len2) 方法（抛出 java.lang.IllegalArgumentException 的地方），你会看到当没有观察到下一个条件时抛出异常：

[mergeHi] Merges two adjacent runs in place, in a stable fashion. The first element of the first run must be greater than the first element of the second run (a[base1] > a[base2]), and the last element of the first run (a[base1 + len1-1]) must be greater than all elements of the second run.

检查哪些元素违反了此规则，您很可能会发现差异。

Answer 4

对于像这样的调试问题，我建议使用日志记录方式。

在异常发生时检查或打印出传递给比较器的值的问题是这些值的结果可能实际上并不正确。但是，它可能与之前不正确的结果不一致。

您可以使用 println 或实际的日志记录框架。或者，由于您的数据集非常大（如果我从您的其他问题中没记错的话），您可以将比较的元素和结果记录到内部数据结构中，然后在排序引发异常后以您喜欢的任何形式将其转储出来。

如果最后一次比较是在MyObject1和MyObject2之间，则在日志中向后搜索涉及这些对象的其他比较。这两个对象之间可能与另一个比较有直接冲突，或者可能存在中间 MyObject3。或者，不幸的是，在发现冲突之前，您可能必须遵循任意长的依赖链：

mo1 < mo2 < mo3 < ... < moN < mo1

但是关于导致不一致的原因的所有信息都应该在日志文件的某个地方。

Java 集合排序：DEBUG/VERBOSE "Comparison method violates its general contract:" 错误的根本原因

Java Collections sort: DEBUG/VERBOSE the RootCause of "Comparison method violates its general contract:" errors

java

sorting

collections

comparator