文档章节

图解JDK7的Comparison method violates its general contract异常

focus_逸
 focus_逸
发布于 2016/08/29 10:27
字数 1714
阅读 12
收藏 0

Axb的自我修养

首页

图解JDK7的Comparison method violates its general contract异常

目录

[显示]

1.摘要

前一阵遇到了一个使用Collections.sort()时报异常的问题,发现问题的原因是JDK7的排序实现改为了TimSort,之后我们又进一步研究了一下这个神奇的算法。

2.背景

先说一下为什么要研究这个异常,前几天线上服务器发现日志里有偶发的异常:

 

 

1

2

3

4

5

6

7

8

9

java.lang.IllegalArgumentException: Comparison method violates its general contract!

at java.util.TimSort.mergeHi(TimSort.java:868)

  at java.util.TimSort.mergeAt(TimSort.java:485)

  at java.util.TimSort.mergeCollapse(TimSort.java:408)

at java.util.TimSort.sort(TimSort.java:214)

  at java.util.TimSort.sort(TimSort.java:173)

  at java.util.Arrays.sort(Arrays.java:659)

  at java.util.Collections.sort(Collections.java:217)

...

 

出错部分的代码如下:

 

 

1

2

3

4

5

6

7

List<Integer> list = getUserIds();

Collections.sort(list, new Comparator<Integer>() {

    @Override

    public int compare(Integer o1, Integer o2) {

        return o1>o2?1:-1;

    }

});

 

google了一下:JDK7中的Collections.Sort方法实现中,如果两个值是相等的,那么compare方法需要返回0,否则可能会在排序时抛错,而JDK6是没有这个限制的。

这个问题在测试时并没有出现,线上也只是小概率复现,如何稳定的复现这个问题?看了一下源代码,抛出异常的那段源代码让人根本摸不着头脑:

 

 

1

2

3

if (len2 == 0) {

    throw new IllegalArgumentException("Comparison method violates its general contract!");

}

 

为了解开这个困惑,我们对java实现的Timsort代码做了一些分析。

3.Timsort概述

TimSort排序是一种优化的归并排序,它将归并排序(merge sort) 与插入排序(insertion sort) 结合,并进行了一些优化。对于已经部分排序的数组,时间复杂度远低于 O(n log(n)),最好可达 O(n),对于随机排序的数组,时间复杂度为 O(nlog(n)),平均时间复杂度 O(nlog(n))。

它的整体思路是这样的:

  1. 遍历数组,将数组分为若干个升序或降序的片段,(如果是降序片段,反转降序的片段使其变为升序),每个片段称为一个Runtask
  2. 从数组中取一个RunTask,将这个RunTask压栈。
  3. 取出栈中相邻两个的RunTask,做归并排序,并将结果重新压栈。
  4. 重复(2),(3)过程,直到所有数据处理完毕。

这篇文章就不再过多的阐述Timsort整体思路了,有兴趣可以参考[译]理解timsort, 第一部分:适应性归并排序(Adaptive Mergesort)

4.Timsort的归并

重点说一下Timsort中的归并。归并过程相对普通的归并排序做了一定的优化,假如有如下的一段数组:

normal1

  1. 首先把数组拆成两个RunTask,这里称为A段和B段,注意,A段和B段在物理地址上是连续的:
    normal1

  2. A段的起点为base1,剩余元素数量为len1;B段起点为base2,剩余元素数量为len2。取B点的起点值B[base2],在A段中进行二分查找,将A段中小于等于B[base2]的段作为merge结果的起始部分;再取A段的终点值a[base1 + len1 – 1],在B段中二分查找,将B段中大于等于a[base1 + len1 – 1]值的段作为结果的结束部分。

    更形象的说,这里把待归并的数据“掐头去尾”,只需要合并中间的数据就可以了:
    normal1

  3. 之后需要创建一个tmp数组,大小为B段截取后的大小,并把B段剩余的数据拷贝过去,因为合并过程中这些数据会被覆盖掉。

    程序会记录corsor1和corsor2,这是待归并数据的指针,初始位置在A段和tmp段的末尾。同时会记录合并后数组的dest指针,位置在原B段的末尾。

    这里还有一个小优化:生成dest指针时会直接把A段cursor1指向的数据拷贝到B段末尾,同时cursor–,dest–。因为之前(2)步的时候已经保证了arr[cursor1]>arr[dest]
    normal1

  4. 进行归并排序,这里每次归并比较时会记录A和tmp段比较“胜利(大于对方)”的次数,比较失败(小于对方)时会把胜利数清零。当有一个段的数据连续N次胜利时会激活另一个优化策略,在这里假设N为4,下图已经是A段连续胜利了4次的情况:
    normal1

  5. 如果连续胜利N次,那么可以假设A段的数据平均大于B段,此时会用tmp[cursor2]的值在A[base0]至A[cursor1]中查找第一个小于tmp[cursor2]的索引k,并把A[k+1]到A[cursor1]的数据直接搬移到A[dest-len,dest]。

    对于例子中的数据,tmp[cursor2]=8,在A数组中查找到小于8的第一个索引(-1),之后把A[0,1]填充到A[dest-1,dest],cursor1和dest指针左移两个位置。
    normal1

  6. 如果cursor1>=0,之后会再用curosr1指向的数据在tmp数组中查找,由于这里cursor1已经是-1了,循环结束。

  7. 最后把tmp里剩余的数据拷贝到A数组的剩余位置中,结束。
    normal1

5.异常情况下Timsort的归并

假设这里实现的compare(obj o1,obj o2)如下:

 

 

1

2

3

public int compare(Integer o1, Integer o2) {

    return o1>o2?1:-1;

}

 

  1. 仍然是分成A,B两段:
    normal1

  2. 在“掐头去尾”的时候,这时会有一些变化,程序执行到compare(B[base2],A[base1])时返回-1,A的左侧留下了两个应该被切走的“5”。
    normal1

  3. 接下来是正常的归并过程。
    normal1

  4. 这里同样会触发“胜利”>N次逻辑
    normal1

  5. 在A[base1,cursor1]中查找小于tmp[cursor2]的元素,复制,cursor1和dest左移两位。
    normal1

  6. 此时再用A[cursor1]在tmp中查找,tmp中所有的数据都被移入A数组,cursor2、dest左移4位。tmp2剩余元素的数量(len2)为0。
    normal1

注意!

在第6步查找的时候,有A[base1+1]<tmp[0](tmp[0]的值等于没有合并之前的B[base2])。
而第2步时,有B[base2]<A[base1]
而最初生成RunTask的时候,有A[base1]<=A[base1+1]
连起来就是B[base2]<A[base1]<=A[base1+1]<B[base2],这显然是有问题的。

所以,当len2==0时,会抛出“Comparison method violates its general contract”异常。问题复现的条件是触发“胜利N次”的优化,并且存在类似(A[base1]==A[base1+x])&&(A[base1+x]==B[base2])的数据排列。这里应该还有几种另外的触发条件,精力有限,就不再深究了。

6.参考

TimSort in Java 7 OpenJDK 源代码阅读之 TimSort


  • 解决方案:
  • 1.JVM加入如下参数-Djava.util.Arrays.useLegacyMergeSort=true,表示使用JDK6的排序算法

    2.按照规定的比较规则进行值的返回,a==b 返回 0,ab 返回 1

本文转载自:http://blog.2baxb.me/archives/993

focus_逸
粉丝 0
博文 32
码字总数 6314
作品 0
珠海
高级程序员
私信 提问
JDK7版本运行抛出异常:Comparison method violates its general contract

最近在学Java,后续尝试用Java在云服务器上做个项目 不过在做一个年龄排序题目的时候,JDK7版本运行抛出异常:Comparison method violates its general contract。 下面是代码: import jav...

云非絮
2016/12/07
1K
6
JDK7-Collections.sort()报Comparison method violates its general contract异常

记录在 JDK7 下使用 Collections.sort() 排序偶发的一个异常,以前在 JDK1.6 下面没有这个问题: Comparison method violates its general contract 发生问题的代码段: 一个很简单的排序,在...

山哥
2016/09/12
119
0
记一次线上处理的用户反馈

今天突然有用户反馈各个端都不能使用我们的产品了,出于经验,应该是和最近的一次上线有关,最近的一次上线是升级java版本,1.6->1.8。 按照用户反馈,立刻去线上grep各个机器这个用户的错误...

selfless
2016/07/31
23
0
Comparison method violates its general contract!

在使用spark RDD中,需要进行二次排序,二次排序需要使用到scala List的sortWith(compare),需传递一个比较函数compare给sortWith,这个时候会报如标题所示的错误。 val rdd1 = rdd.groupBy...

cjun1990
2016/03/31
631
0
feilong-core 1.10.5,让 Java 开发更简便的工具包

feilong-core 1.10.5 发布了。feilong-core 是一个让 Java 开发更简便的工具包, 可以让你从大量重复的底层代码中脱身,提高工作效率; 让你的代码更简炼,易写、易读、易于维护; 本次升级共有 ...

飞天奔月
2017/07/31
531
3

没有更多内容

加载失败,请刷新页面

加载更多

研究下这代码,用到了guava和线程池

import com.google.common.util.concurrent.FutureCallback;import com.google.common.util.concurrent.Futures;import com.google.common.util.concurrent.ListenableFuture;import c......

暗中观察
25分钟前
3
0
《css 揭秘》 之垂直居中的实现

最近看了 Lea Verou 的 《css揭秘》一书,让我对自己的 css学习产生了深深的怀疑。这本书真是太棒了,里面涉及到很多优雅又有趣的效果实现,真的是非常棒。如果你有时间,十分建议你去看看。...

IrisHuang
31分钟前
3
0
java 抽象类(2)

/*需求: 描述一个图形、圆形、 矩形三个类。不管哪种图形都会具备计算面积与周长的行为,但是每种图形计算的方式不一致而已。常量的命名规范:全部字母大写,单词与单词 之间 使用下...

hellation_
33分钟前
2
0
总结:堆和栈

堆 堆比较好理解,即存放对象的地方。这里的对象由GC管理 1、类变量(static修饰的变量):在程序加载时系统就为它在堆中开辟了内存,堆中的内存地址存放于栈以便于高速访问。静态变量的生命...

浮躁的码农
39分钟前
1
0
JavaScript 新语法详解:Class 的私有属性与私有方法

译者按: 为什么偏要用**#**符号? 原文:JavaScript's new #private class fields 译者:Fundebug 本文采用意译,版权归原作者所有 proposal-class-fields与proposal-private-methods定义了 ...

Fundebug
41分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部