轉(zhuǎn)自原文地址:
http://blog.2baxb.me/archives/993
1.摘要
前一陣遇到了一個使用Collections.sort()時報異常的問題嘀倒，跟小伙伴@zhuidawugui 一起排查了一下根竿，發(fā)現(xiàn)問題的原因是JDK7的排序?qū)崿F(xiàn)改為了TimSort，之后我們又進(jìn)一步研究了一下這個神奇的算法。
2.背景
先說一下為什么要研究這個異常若河，前幾天線上服務(wù)器發(fā)現(xiàn)日志里有偶發(fā)的異常：
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)
出錯部分的代碼如下：
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方法實(shí)現(xiàn)中，如果兩個值是相等的，那么compare方法需要返回0顺又，否則可能會在排序時拋錯，而JDK6是沒有這個限制的等孵。
這個問題在測試時并沒有出現(xiàn)稚照，線上也只是小概率復(fù)現(xiàn)，如何穩(wěn)定的復(fù)現(xiàn)這個問題俯萌？看了一下源代碼果录，拋出異常的那段源代碼讓人根本摸不著頭腦：
if (len2 == 0) {
throw new IllegalArgumentException("Comparison method violates its general contract!");
}
為了解開這個困惑，我們對java實(shí)現(xiàn)的Timsort代碼做了一些分析咐熙。
3.Timsort概述
TimSort排序是一種優(yōu)化的歸并排序弱恒，它將歸并排序(merge sort) 與插入排序(insertion sort) 結(jié)合，并進(jìn)行了一些優(yōu)化棋恼。對于已經(jīng)部分排序的數(shù)組返弹，時間復(fù)雜度遠(yuǎn)低于 O(n log(n))，最好可達(dá) O(n)蘸泻，對于隨機(jī)排序的數(shù)組琉苇，時間復(fù)雜度為 O(nlog(n))，平均時間復(fù)雜度 O(nlog(n))悦施。
它的整體思路是這樣的：
- 遍歷數(shù)組并扇，將數(shù)組分為若干個升序或降序的片段，（如果是降序片段抡诞，反轉(zhuǎn)降序的片段使其變?yōu)樯颍┣钣迹總€片段稱為一個Runtask
- 從數(shù)組中取一個RunTask土陪，將這個RunTask壓棧。
- 取出棧中相鄰兩個的RunTask肴熏，做歸并排序鬼雀，并將結(jié)果重新壓棧。
- 重復(fù)(2),(3)過程蛙吏，直到所有數(shù)據(jù)處理完畢源哩。
這篇文章就不再過多的闡述Timsort整體思路了，有興趣可以參考[譯]理解timsort, 第一部分：適應(yīng)性歸并排序(Adaptive Mergesort)
4.Timsort的歸并
重點(diǎn)說一下Timsort中的歸并鸦做。歸并過程相對普通的歸并排序做了一定的優(yōu)化励烦，假如有如下的一段數(shù)組：
-
首先把數(shù)組拆成兩個RunTask，這里稱為A段和B段泼诱，注意坛掠，A段和B段在物理地址上是連續(xù)的：
normal1 -
A段的起點(diǎn)為base1，剩余元素數(shù)量為len1治筒；B段起點(diǎn)為base2屉栓，剩余元素數(shù)量為len2。取B點(diǎn)的起點(diǎn)值B[base2]耸袜，在A段中進(jìn)行二分查找友多，將A段中小于等于B[base2]的段作為merge結(jié)果的起始部分；再取A段的終點(diǎn)值a[base1 + len1 – 1]堤框，在B段中二分查找夷陋，將B段中大于等于a[base1 + len1 – 1]值的段作為結(jié)果的結(jié)束部分。
更形象的說胰锌，這里把待歸并的數(shù)據(jù)“掐頭去尾”骗绕，只需要合并中間的數(shù)據(jù)就可以了：
normal1 -
之后需要創(chuàng)建一個tmp數(shù)組，大小為B段截取后的大小资昧，并把B段剩余的數(shù)據(jù)拷貝過去酬土，因?yàn)楹喜⑦^程中這些數(shù)據(jù)會被覆蓋掉。
程序會記錄corsor1和corsor2格带，這是待歸并數(shù)據(jù)的指針撤缴，初始位置在A段和tmp段的末尾。同時會記錄合并后數(shù)組的dest指針叽唱，位置在原B段的末尾屈呕。
這里還有一個小優(yōu)化：生成dest指針時會直接把A段cursor1指向的數(shù)據(jù)拷貝到B段末尾，同時cursor–,dest–棺亭。因?yàn)橹?2)步的時候已經(jīng)保證了arr[cursor1]>arr[dest]
normal1 -
進(jìn)行歸并排序虎眨，這里每次歸并比較時會記錄A和tmp段比較“勝利（大于對方）”的次數(shù)，比較失敗（小于對方）時會把勝利數(shù)清零嗽桩。當(dāng)有一個段的數(shù)據(jù)連續(xù)N次勝利時會激活另一個優(yōu)化策略岳守，在這里假設(shè)N為4，下圖已經(jīng)是A段連續(xù)勝利了4次的情況：
normal1 -
如果連續(xù)勝利N次碌冶，那么可以假設(shè)A段的數(shù)據(jù)平均大于B段湿痢，此時會用tmp[cursor2]的值在A[base0]至A[cursor1]中查找第一個小于tmp[cursor2]的索引k，并把A[k+1]到A[cursor1]的數(shù)據(jù)直接搬移到A[dest-len,dest]扑庞。
對于例子中的數(shù)據(jù)譬重，tmp[cursor2]=8，在A數(shù)組中查找到小于8的第一個索引（-1）罐氨，之后把A[0,1]填充到A[dest-1,dest]害幅，cursor1和dest指針左移兩個位置。
normal1 如果cursor1>=0岂昭，之后會再用curosr1指向的數(shù)據(jù)在tmp數(shù)組中查找，由于這里cursor1已經(jīng)是-1了狠怨，循環(huán)結(jié)束约啊。
-
最后把tmp里剩余的數(shù)據(jù)拷貝到A數(shù)組的剩余位置中，結(jié)束佣赖。
normal1
5.異常情況下Timsort的歸并
假設(shè)這里實(shí)現(xiàn)的compare(obj o1,obj o2)如下：
public int compare(Integer o1, Integer o2) {
return o1>o2?1:-1;
}
-
仍然是分成A恰矩，B兩段：
normal1 -
在“掐頭去尾”的時候，這時會有一些變化憎蛤，程序執(zhí)行到compare(B[base2],A[base1])時返回-1外傅，A的左側(cè)留下了兩個應(yīng)該被切走的“5”。
normal1 -
接下來是正常的歸并過程俩檬。
normal1 -
這里同樣會觸發(fā)“勝利”>N次邏輯
normal1 -
在A[base1,cursor1]中查找小于tmp[cursor2]的元素萎胰，復(fù)制，cursor1和dest左移兩位棚辽。
normal1 -
此時再用A[cursor1]在tmp中查找技竟，tmp中所有的數(shù)據(jù)都被移入A數(shù)組，cursor2屈藐、dest左移4位榔组。tmp2剩余元素的數(shù)量（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]，這顯然是有問題的。
所以爱态，當(dāng)len2==0時谭贪，會拋出“Comparison method violates its general contract”異常。問題復(fù)現(xiàn)的條件是觸發(fā)“勝利N次”的優(yōu)化锦担，并且存在類似(A[base1]==A[base1+x])&&(A[base1+x]==B[base2])的數(shù)據(jù)排列俭识。這里應(yīng)該還有幾種另外的觸發(fā)條件，精力有限洞渔，就不再深究了套媚。
case 重現(xiàn)
package com.sparrow.test;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
public class DictionaryTest {
public static void main(String[] args) {
//exception
int[] array = new int[]{1, 2, 3, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
//array = new int[]{2, 3, 2, 2, 3, 2, 3, 2, 2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
// 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
List<DictionaryEntry> list = new ArrayList<>();
Set<DictionaryEntry> set = new TreeSet<>();
for (int i = 0; i < array.length; i++) {
DictionaryEntry entry = new DictionaryEntry();
entry.setItemId(i);
entry.setScore(new BigDecimal(array[i]));
list.add(entry);
set.add(entry);
}
System.out.println(set.size());
Collections.sort(list);
System.out.println(list.size());
}
public static class DictionaryEntry implements Comparable<DictionaryEntry> {
public DictionaryEntry() {
}
private Integer itemId;
private BigDecimal score;
public BigDecimal getScore() {
return score;
}
public void setScore(BigDecimal score) {
if (score != null) {
this.score = score.setScale(5, RoundingMode.HALF_UP);
} else {
this.score = new BigDecimal(0);
}
}
public Integer getItemId() {
return itemId;
}
public void setItemId(Integer itemId) {
this.itemId = itemId;
}
@Override
public int compareTo(DictionaryEntry o) {
//TreeSet o.score.compareTo(this.score)==0時去重
//手動設(shè)置非0時,throw new IllegalArgumentException("Comparison method violates its general contract!");
//-Djava.util.Arrays.useLegacyMergeSort=true 解決兼容
return o.score.compareTo(this.score) == 0 ? -1 : o.score.compareTo(this.score);
}
}
}
