Java 集合排序 : DEBUG/VERBOSE the RootCause of "Comparison method violates its general contract:" errors

Question

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

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。我不是在问上面的代码有什么问题。我已经问过并得到了答复 Java Collections sort: Comparison method violates its general contract在这里我要问我如何自己调试/监控这些类型的错误。

Answer 1

异常是非常 self 描述的，当提供的 Comparator 不是可传递的时，就会发生违反契约(Contract)的情况。为什么您的 Comparator 不是可传递的？因为你提供 not accurate subtraction浮点值。这对于 Java 和其他编程语言来说是正常的。换句话说，您假设 0.1 - 0.1 会产生 0，但它不会。

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

我可以建议您使用 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.

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