Collections.sort() 出现 IllegalArgumentException?因为它:TimSort

使用 Collections.sort() 对 ArrayList 数组进行排序时,偶现了 IllegalArgumentException 异常,于是追根溯源,对使用的排序算法-TimSort,出现异常的原因及其解决方案进行了如下的总结。

在灰度期间,上报了一个排序的 bug,如下所示:

1
2
3
4
5
6
7
java.lang.IllegalArgumentException: Comparison method violates its general contract!
java.util.TimSort.mergeLo(TimSort.java:761)
java.util.TimSort.mergeAt(TimSort.java:497)
java.util.TimSort.mergeCollapse(TimSort.java:424)
java.util.TimSort.sort(TimSort.java:210)
java.util.Arrays.sort(Arrays.java:1998)
java.util.Collections.sort(Collections.java:1900)

定位到业务代码,实现的比较器如下:

1
2
3
4
5
6
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1>o2?1:-1;
}
});

跟踪系统实现排序的地方,在 JDK 7 中,对比较器的实现做了比较严格的限制,当俩个值相等(o1 = o2)时,需要保证 compare(o1, o2) = 0 ,而在 JDK 6 使用时是没问题的。为了一探究竟,就定位到了实现 sort 算法的位置:

1
2
3
4
5
6
7
8
9
10
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}

JDK ≥ 7 在这里更新了排序算法,如果指定了 LegacyMergeSort.userRequested 值为 true,则使用老的 ( JDK < 7)mergeSort;如果没有指定,则使用 TimSort。老的归并排序没有产生过这种异常,那为什么 Java 竟然会放弃兼容,替换成 TimSort 后会异常呢?接下来我们先深入 TimSort 的排序原理,再来看看出错的原因及其解决方案。

TimSort 原理

TimSort 结合了归并排序(merge sort)和插入排序(insertion sort),它基于一个简单的事实:大部分数据都是部分有序的。Youtube 上有一个很直观的 TimSort 排序视频:https://www.youtube.com/watch?v=NVIjHj-lrT4,可以通过这段视频对算法的过程有一个感性的了解。

TimSort 算法定义数组中一个有序的片段为 run,每个 run 都要求严格升序或降序,来保证算法的稳定性,如下所示:

run

划分 run

TimSort 首先将待排序的数组,按照严格升序或降序(保证算法稳定性)划分一段一段的 run,如果为逆序则进行翻转,但是它的长度不能小于 minRun 这个阈值;如果长度小于 minRun,则把之后的数按照二分查找插入到该区间直到满足最小的长度要求。

这里我们定义一组待排序的数列:

待排序

假设最小的 run 长度为 minRun = 4 ,则上述待排序数组可以分为以下不同的 run 区间:

run区间

  • 如果该数组是一个完全正序或逆序的,则只需要划分一个 run,这时排序只需要 O(N) 的时间。
  • 划分过程中,如果长度小于 minRun,则会把后边的数按照二分查找算法插入补齐,如果是最后剩余的部分,则单独组成一个 run。

run 合并

TimSort 第二步就是对划分的 run 进行压栈,对于在栈顶的 run[i],必须同时满足以下条件:

1
2
1. runLen[i - 2] > runLen[i - 1] + runLen[i]
2. runLen[i - 1] > runLen[i]

如果有一个不满足,则会把最短的 2 个 run 进行归并成一个新的 run。接下来看看上述待排序的数组是如何把 run 进行合并的。

归并_1

当把 run[1] 压栈时,可以看到 runLen[0] < runLen[1] ,所以需要把俩个 run 进行归并,合成一个新的 run 再重新压入栈中。

归并_2

之后我们一次把 run[1](10 > 5),run[2](10>5+4 & 5>4)入栈,因为在栈顶的 run 都满足约束条件。当把 run[3] 入栈时,发现 runLen[1] > runLen[2] + runLen[3] 不成立,所以需要把 run[3] 和 run[2] 合并。之后也仍然按照这样的规则进行,当栈空时,也就排好序了。

俩个 run 的归并排序

TimSort 把 run 压人栈顶,如果不满足俩个约束条件,会把较短的俩个 run 进行归并排序,这里的归并排序相对普通的归并做了俩个优化点,都是充分利用一个简单的事实:大部分数据都是部分有序的。

Galloping Mode 减少参与归并的数据

假若有以下俩个 run ,不满足约束条件需要进行合并。设 run[0] 别称为 A,首地址为 base1,长度为 len1;run[1] 别称为 B,首地址为 base2,长度为len2。

归并排序_1

在 Galloping Mode 下,会根据以下条件查找对应区间:

  • 取 B 片段的起始值 B[base2],在 A 片段中使用二分查找,则 A 片段中小于等于 B[base2] 段就是最终排好序的起始部分。
  • 取 A 片段的终点值 A[base1 + len1 - 1],在 B 片段中进行二分查找,则 B 片段中大于等于 A[base1 + len1 - 1] 的区间就是最终归并排序的结束部分。

归并排序_2

这里充分利用了部分数据有序这个事实,形象的“掐头去尾”,这样最终需要归并的数据只有中间的俩段数据。

连续胜利 MIN_GALLOP 次继续触发 Galloping

对 A 和 B 的俩个剩余片段,添加俩个指针,cursor1 指向 A 片段的末尾 cursor1 = base1 + len1 - 1 ,dest 指向 B 的剩余片段的末尾 dest = base2 + len2 - 1

因为在上一步骤中保证了 A [cursor1] > B[dest],所以会先把 A 片段的最后一个数据直接拷贝到 B 片段的末尾,同时 cursor--,dest--

剩余的俩段区间,选择长度较小的一段复制到临时的 tmp 数组(节省内存开销),这里 B 片段的区间小一点,所以会放到临时数组的是 B 的剩余归并片段。

归并排序_3

接着对 A 片段和 tmp 片段做普通的归并,A[cursor1] 和 tmp[cursor2] 进行比较,把比较大数移到 A[dest],同时 dest 和对应片段的指针减1。

在俩个片段的比较过程中,会记录 A 片段和 tmp 片段比较胜利(大于对方)次数,比较失败会直接把胜利次数清零。当某个片段的胜利次数大于 minGallop ,会进一步触发 Galloping 。假设 minGallop = 4 ,则 A 片段在胜利 4 次后会如下图所示,

归并排序_4

触发 Galloping

取 tmp 片段的终点值 tmp[cursor2],在 A 片段中二分查找到小于 tmp[cursor2] 的索引 k,则 A[k + 1, cursor1] 这个片段都大于 tmp[cursor2],这时就可以直接把 A[k + 1, cursor1] 复制到 A[dest - len, dest](len = cursor1 - k + 1)。如图找到的 k = -1 ,把俩个 10 复制过去后,cursor1 就到了 k 的位置了。

归并排序_5

如果 cursor1 >= 0 ,俩个片段会继续进行归并比较,当连胜 minGallop 次才会又一次出发 Galloping。这里 cursor1 = -1 ,所以接下来只要把tmp 剩余的数据拷贝到 A[base1, dest] 即可。

归并排序_6

总结

TimSort 排序算法综合了折半插入(二分查找)排序和归并排序,侧重优化了部分数据有序的情况,减少了对升序部分的回溯和对降序部分的性能倒退(快速排序在有序的情况下会退化到O(N^²))。其算法思路总结如下

  • 当待排序数组长度小于 MIN_MERGE(MIN_MERGE = 32),会使用没有归并的 TimSort,也就是会先进行一次 Galloping 找到左边有序的一个片段,再对后边的数据进行二分查找(折半插入)排序。
  • 划分长度不小于 minRun 且严格升序(降序则翻转,不足则用后边数据二分查找插入)的 run 片段,并压人栈中,当不满足约束条件时,进行归并
  • 在归并过程中,会先进行 Galloping,“掐头去尾”,再进行中间俩个片段的归并
  • 俩个片段比较过程中,若某个片段连胜 MIN_GALLOP,则又会进行一次 Galloping,进行”掐头” 或“去尾”,否则就退化成普通的归并排序。

TimSort 的时间和空间复杂度如下表:

Algorithm Average Best Worst extra space stable
TimSort O(NlogN) O(N) O(NlogN) O(N) 稳定

在完全正序或逆序的情况下,TimSort 只需要 O(N) 的时间和 O(1) 的空间,空间消耗主要来自于俩个片段归并过程中创建的临时数组。

出错原因

回到在业务中使用 Collections.sort() 时,当 Comparator 没有实现俩个数据相等情况下返回 0 的情况下,会出现 IllegalArgumentException。假设这里实现的比较器如下:

1
2
3
4
5
6
new Comparator<Inteager>() {
@Override
public int compare(Inteager o1, Inteager o2) {
return o1 > o2 ? 1 : -1;
}
});

则当 o1 = o2 时,有如下等式成立:

  • compare(o1,o2) < 0
  • compare(o2,o1) < 0

这里我们假设现在有俩个 run 需要进行归并:

归并排序出错_0

1、在进行 Galloping “掐头” 过程中,执行 compare(B[base2], A[base1 + hint]) 过程中,因为 compare(o1,o2) < 0 (o1 = o2),所以此时 B 片段中的 5 是比 A 片段中的俩个 5 都要小,所以 A 片段的 5 都会保留下来。

归并排序出错_1

之后中间俩个片段进行正常的归并,当连胜 minGallop(minGallop = 4)次后会又一次触发 Galloping。归并排序出错_3

2、在这次 Galloping 中,会在 A 片段中查找比 tmp[cursor2] 还要小的位置 k,并把 A[K + 1, cursor1] 移到 A[dest - len, dest] 中,同时 cursor1 和 dest 左移俩位。

归并排序出错_4

3、接下来俩个片段在归并过程中,tmp[cursor2] 连续 4 次比 A[cursor1] 大,又一次触发 Galloping。

归并排序出错_5

4、在这次 Galloping过程中,取 A 片段的 A[cursor1] 的值,去 tmp 片段中查找大于 A[cursor1] 的区间。使用比较器 compare(A[cursor1],tmp[k]),因为 compare(o1,o2) < 0 (o1 = o2),所以此时 A 片段中的 5 是小于 tmp 片段中的 5。tmp 的数据会依次拷贝到 A[dest] 后,cursor2的指针到-1了,且此时 tmp 数组的长度 len2 为 0。

归并排序出错_6

5、因为 tmp 的长度(len2)为 0,会触发 mergeHi 中如下的异常

1
2
3
4
} else if (len2 == 0) {
throw new IllegalArgumentException(
"Comparison method violates its general contract!");
} else {

我们再回顾一下上边的过程,在第 1 步“掐头去尾”中,我们保证 A[base1] > B[base2],在第 4 步中,cursor2 最终指到 -1 了,所以有 A[cursor1] < tmp[0],即:A[base1 + 1] < B[base2]。综上可以列出以下等式:

  • A[base1] <= A[base1 + 1]
  • A[base1] > B[base2]
  • A[base+1] < B[base2]

A[base1] <= A[base1+1]<B[base2]<A[base1],显然不合情理。

从另一个角度来看:在 mergeHi 中把后边的 B 片段取出放到临时数组 tmp 里,B 片段的第一个数据 B[base2] 肯定是最后一个才会放进去的,因为把小于 B[base2] 的数据第一步就掐走了,在留下的 A 片段里肯定都是不小于 B[base2] 的数据。

因为不满足比较器的自反性(compare(o1, o2) ≠ compare(o2 , o1),if o1 = o2),当有相等的值,且俩个片段在进行 Galloping 时正好用了俩次 compare(一次 compare(o1, o2),一次compare(o2, o1)),这时便有可能会触发这个异常。

解决方案

经过对 TimSort 源码及出错的原因分析,我们可以很快的得到如下俩种解决方案。

严格实现比较器

在创建比较器 Comparator 实现 compare() 方法中,当俩个值相等(o1 = o2)时,必须保证 compare(o1, o2) = 0

使用旧的排序算法

JDK 6 及以下的版本中,使用的排序算法是普通的归并排序,不需要 compare(o1, o2) = 0(o1 = o2) 这么严格的条件。所以第二种解决方法仍然使用老版本的归并排序算法,设置如下:

1
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");