java - 比较方法违反了它的总合同!(排序期间集合中重复的元素)
问题描述
我知道有很多主题相同的主题,但在我看来,这个案例有点不同,并且在 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)
所以看起来,在排序过程中不可能依赖收集,因为它处于脏状态。这种行为是否记录在某处?
解决方案
让我们通过记录 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) 会抛出这样的异常。
推荐阅读
- azure - 为什么在 addKey/addPassword 请求期间,Azure 广告应用程序中的证书/客户端机密会消失?
- azure-data-lake - 将单个 json 从 azure iot hub 存储到 datalake2
- java - @Sneaky Throws 在龙目岛的应用
- android - 在后台线程中使用 MPAndroidChart 会引发 java.lang.RuntimeException:无法在未调用 Looper.prepare() 的线程内创建处理程序
- html - 如何在css中居中多个按钮?
- javascript - 如何将选择链接到我的表头?
- python - 是否可以访问先前训练的 tensorflow 模型?
- python - python可以规范化对象数组吗?
- python - 如何更新子图?
- c# - 获取放置在图像中的组件的新位置