服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - java中排序报:Comparison method violates its general contract异常的解决

java中排序报:Comparison method violates its general contract异常的解决

2020-11-20 10:26Pulpcode Java教程

这篇文章主要给大家介绍了关于java中排序报:Comparison method violates its general contract异常的解决方法,文中介绍的非常详细,对大家具有一定的参考学习价值,需要的朋友们下面来一起看看吧。

前言

上周线上的一段排序java代码出现了一个Comparison method violates its general contract,在解决这个问题的途中学到了一些知识这里总结分享一下。

异常原因

这个排序导致的异常将会在java7以上的版本出现,所以如果你的JDK从6升级到了7或者8,那一定要小心此异常。

在java7的兼容列表中,就有对此排序不兼容的说明:

?
1
2
3
4
5
6
Area: API: Utilities
Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException
Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation.
If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.
Nature of Incompatibility: behavioral
RFE: 6804124

我从资料中查阅到java7开始引入了Timsort的排序算法。我之前一直以为大部分标准库的内置排序算法都是快速排序。现在才得知很多语言内部都使用Timsort排序。随后我在wiki百科上找到了这样一句话:

t was implemented by Tim Peters in 2002 for use in the Python programming language.

所以这个排序自然是以他命名的。

随后我又在网上找到了这样一张图排序比较的图:

java中排序报:Comparison method violates its general contract异常的解决

可以发现,Timsort在表现上比QuickSort还要好。

这篇博客不去详细讨论Timsort的实现(看上去这个算法还挺复杂的),我可能会写另一篇博客单独讨论Timsort,简单来说Timsort结合了归并排序和插入排序。这个算法在实现过程中明确需要:严格的单调递增或者递减来保证算法的稳定性。

java中排序报:Comparison method violates its general contract异常的解决

  • sgn(compare(x, y)) == -sgn(compare(y, x))
  • ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0
  • compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z

看上去很像离散数学课中学习的集合的对称性,传递性的关系。

所以异常的原因是因为排序算法不够严谨导致的,实际上业务上的代码经常不如纯技术上的严谨。比如对于这样一个算法:

选出航班中的最低价

那如果两个相等低价同时存在,按照寻找最低价的逻辑如果这么写:

?
1
2
3
if (thisPrice < lowPrice){
 lowPrice = thisPrice;
}

那低价这个位置就是“先到先得”了。

但如果这么实现:

?
1
2
3
if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}

那后面的低价就会覆盖前面的,变成了“后来者居上”。编程中经常遇到先到先得和后来者居上这两个问题。

所以对于上面那个需要提供严谨的判断大小比较函数实现。所以如果是这样的:

?
1
return x > y ? 1 : -1;

那么就不符合此条件。

不过我们逻辑要比这个复杂,其实是这样一个排序条件。按照:

  • 价格进行排序,如果价格相等则起飞时间靠前的先排。
  • 如果起飞时间也相等,就会按照:
  • 非共享非经停>非经停>非共享>经停的属性进行优先级选择,如果这些属性都全部相等,才只能算是相等了。

所以这个判断函数的问题是:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public compareFlightPrice(flightPrice o1, flightPrice o2){
 // 非经停非共享
 if (o1.getStopNumber() == 0 && !o1.isShare()) {
 return -1;
 } else if (o2.getStopNumber() == 0 && !o2.isShare()) {
 return 1;
 } else {
 if (o1.getStopNumber() == 0) {
  return -1;
 } else if (o2.getStopNumber() == 0) {
  return 1;
 } else {
  if (!o1.isShare()) {
  return -1;
  } else if (!o2.isShare()) {
  return 1;
  } else {
  if (o1.getStopNumber() > 0) {
   return -1;
  } else if (o2.getStopNumber() > 0) {
   return 1;
  } else {
   return 0;
  }
  }
 }
 }
}

这个函数有明显的先到先得的问题,比如对于compareFlightPrice(a, b) ,如果ab都是非共享非经停,那么这个就会把a排到前面,但如果调用compareFlightPrice(b, a) ,b又会排到前面,所以必须判断a是非共享非经停且b不是非共享非经停,才能让a排在前面。

当然除了改比较函数,还有一个解决方式是:给jvm添加启动参数。

?
1
-Djava.util.Arrays.useLegacyMergeSort=true

还需要注意的是,并不一定你的集合中存在相等的元素,并且比较函数不符合上面的严谨定义,就一定会稳定浮现此异常,实际上我们在生产环境出现此异常的概率很小,毕竟java并不会蠢到先去把整个数组都校验一遍,实际上它是在排序的过程中发现你不符合此条件的。所以有可能某种集合顺序让你刚好绕过了此判断。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流,谢谢大家对服务器之家的支持。

原文链接:http://www.pulpcode.cn/2017/06/18/comparison-method-violates-its-general-contractfor-sort/

延伸 · 阅读

精彩推荐