1

我知道有很多主题相同的主题，但在我看来，这个案例有点不同，并且在 javadocs 中没有详细记录。这是代码：

Random random = new Random(0);

var list = new ArrayList<>();
for (int i = 0; i < 60; i++) {
    list.add(random.nextInt());
}

list.sort((x, y) -> {
    int sum = list.stream().reduce(0, Integer::sum);

    System.out.println(sum);

    return Integer.compare(x + sum, y + sum);
});

结果是异常：

-1303811196
-1303811196
.....
-1303811196
-1303811196
-1303811196
-1364558868
-1569607140
-1836181454
-2014724660
-2023409163
-2094470032
-2128134715
2107317277
2107317277
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.base/java.util.TimSort.mergeLo(TimSort.java:781)
    at java.base/java.util.TimSort.mergeAt(TimSort.java:518)
    at java.base/java.util.TimSort.mergeCollapse(TimSort.java:448)
    at java.base/java.util.TimSort.sort(TimSort.java:245)
    at java.base/java.util.Arrays.sort(Arrays.java:1516)
    at java.base/java.util.ArrayList.sort(ArrayList.java:1717)
    at HomeWork6_4.Company.main(Company.java:131)

所以看起来，在排序过程中不可能依赖收集，因为它处于脏状态。这种行为是否记录在某处？

4

1 回答 1

2

让我们通过记录 Comparator 在内部执行的操作来进行调试。为此，我添加了一种特殊的日志记录方法来跟踪比较器的结果。请检查下面的代码

public static void main(String[] args) {
    Random random = new Random(0);
    
    var list = new ArrayList<Integer>();

    for (int i = 0; i < 60; i++) {
        list.add(random.nextInt());
    }
    list.sort(logging((x, y) -> {
        int sum = list.stream().reduce(0, Integer::sum);
        return Integer.compare(x + sum, y + sum);
    }));
}

public static Comparator<Integer> logging(Comparator<Integer> c) {
    return (Integer a, Integer b)-> {
        int r = c.compare(a, b);
        System.err.printf("%7d  %7d => %2d%n", a, b, r);
        return r;
    };
}

比较器对于两个输入 (T a, T b) 的行为如下

(i) returns  less than 0 ,  means a<b
(ii)returns 0 , means a==b
(iii)return greater than 0 , means a>b

如果任何比较器不满足这些规则，我们就说比较器坏了。现在让我们密切关注比较器记录的内容

-723955400  -1155484576 => -1  // broken (a>b but comparator Integer.compare(a+sum,b+sum) returned less than 0)
1033096058  -723955400 =>  1   // broken 
1033096058  -1155484576 => -1
1033096058  -723955400 =>  1
-1690734402  1033096058 =>  1. // broken

这表明Integer.compare(a+sum, b+sum)当您对列表元素应用时，您使用的特定比较器已溢出并导致结果不一致。当使用这种损坏的比较器时，sort(c) 会抛出这样的异常。

于 2020-06-02T18:05:08.007 回答