Java收集器排序:调试/详细显示“比较方法违反其一般约定的RootCause：”错误

Question

有大量的Collections.sort问题的例子，不能轻易解决，通过自我调查或调试。是否有一种调试和详细的方法，哪些对象/比较项会导致以下错误？即MyObject1、MyObject2和MyObject3。我们如何在没有google/堆栈溢出帮助的情况下调试它们？

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 1，2和3.我不是在问上面的代码有什么问题。我已经询问并得到了答案，Java集合排序:比较方法违反了它的一般契约在这里，我在问我如何能够自己调试/监控这些错误。

Answer 1

例外是相当自我描述的，如果Comparator不是传递性的，就会发生违反合同的情况.为什么你的Comparator不是传递性的？因为您正在提供浮点值的不精确减法。对于Java和其他编程语言来说，这是正常的。换句话说，您假设0.1 - 0.1将生成0，但它不会。

看来，减法的结果非常冗长，不能与0进行严格比较。例如，如果您试图使用两个具有相同totalEnergy值的对象对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);
}

还请参见：

• 浮点数不是减法后的预期数。
• 为什么这个减法不等于零？
• 使用==来比较Java中的浮点数有什么问题？

调试过程：

深入JDK的来源。如果您简短地查看一下java.util.TimSort.mergeHi(int base1, int len1, int base2, int len2)方法(其中抛出java.lang.IllegalArgumentException )，您将看到在没有观察到下一个条件时抛出异常：

mergeHi合并两个相邻的运行位置，以稳定的方式运行。第一次运行的第一个元素必须大于第二次运行的第一个元素(abase1 > abase2)，第一次运行的最后一个元素(abase1 + len1-1)必须大于第二次运行的所有元素。

检查哪些元素违反了这条规则，很可能您会发现不一致。

Answer 2

对于这样的调试问题，我建议使用日志样式的appraoch。

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

您可以使用println或实际的日志框架。或者，由于您的数据集相当大(如果我正确地回忆起您的其他问题)，您可以将比较的元素和结果记录到内部数据结构中，然后在排序抛出异常后以任何形式将其转储出去。

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

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

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

Answer 3

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