from：http://www.lifebackup.cn/timsort-java7.html
2012年09月25日 21:57:481. 為什么寫(xiě)這篇文章
這篇文章的根源是在產(chǎn)品中發(fā)現(xiàn)了一個(gè)詭異的bug：只能在產(chǎn)品環(huán)境下重現(xiàn)，在我的本地開(kāi)發(fā)環(huán)境無(wú)法重現(xiàn)，而雙方的代碼沒(méi)有任何區(qū)別。最后用remote debug的方法找到異常所在：
Exception in thread "main" java.lang.IllegalArgumentException: Comparison
method violates its general contract!
Google了這個(gè)錯(cuò)誤，是由于Java 7內(nèi)置的新排序算法導(dǎo)致的。這才猛然想起產(chǎn)品的編譯環(huán)境最近升級(jí)到了Java 7。
2. 結(jié)論
在Java 6中Arrays.sort()和Collections.sort()使用的是MergeSort，而在Java 7中，內(nèi)部實(shí)現(xiàn)換成了TimSort，其對(duì)對(duì)象間比較的實(shí)現(xiàn)要求更加嚴(yán)格：
Comparator的實(shí)現(xiàn)必須保證以下幾點(diǎn)（出自這兒）：
a). sgn(compare(x, y)) == -sgn(compare(y, x))
b). (compare(x, y)>0) && (compare(y, z)>0) 意味著 compare(x, z)>0
c). compare(x, y)==0 意味著對(duì)于任意的z：sgn(compare(x, z))==sgn(compare(y, z)) 均成立
而我們的代碼中，某個(gè)compare()實(shí)現(xiàn)片段是這樣的：
public int compare(ComparatorTest o1, ComparatorTest o2) {
return o1.getValue() > o2.getValue() ? 1 : -1;
}
這就違背了a)原則：假設(shè)X的value為1，Y的value也為1；那么compare(X, Y) ≠ –compare(Y, X)
PS: TimSort不僅內(nèi)置在各種JDK 7的版本，也存在于Android SDK中（盡管其并沒(méi)有使用JDK 7）。
3. 解決方案
3.1) 更改內(nèi)部實(shí)現(xiàn)：例如對(duì)于上個(gè)例子，就需要更改為
public int compare(ComparatorTest o1, ComparatorTest o2) {
return o1.getValue() == o2.getValue() ? 0 :
(o1.getValue() > o2.getValue() ? 1 : -1);
}
3.2) Java 7預(yù)留了一個(gè)接口以便于用戶繼續(xù)使用Java 6的排序算法：在啟動(dòng)參數(shù)中（例如eclipse.ini）添加-Djava.util.Arrays.useLegacyMergeSort=true
3.3) 將這個(gè)IllegalArgumentException手動(dòng)捕獲?。ú煌扑]）
4. TimSort在Java 7中的實(shí)現(xiàn)
那么為什么Java 7會(huì)將TimSort作為排序的默認(rèn)實(shí)現(xiàn)，甚至在某種程度上犧牲它的兼容性（在stackoverflow上有大量的問(wèn)題是關(guān)于這個(gè)新異常的）呢？接下來(lái)我們不妨來(lái)看一看它的實(shí)現(xiàn)。
首先建議大家先讀一下這篇文章以簡(jiǎn)要理解TimSort的思想。
4.1) 如果傳入的Comparator為空，則使用ComparableTimSort的sort實(shí)現(xiàn)。
4.2) 傳入的待排序數(shù)組若小于MIN_MERGE（Java實(shí)現(xiàn)中為32，Python實(shí)現(xiàn)中為64），則
a) 從數(shù)組開(kāi)始處找到一組連接升序或嚴(yán)格降序（找到后翻轉(zhuǎn)）的數(shù)
b) Binary Sort：使用二分查找的方法將后續(xù)的數(shù)插入之前的已排序數(shù)組
4.3) 開(kāi)始真正的TimSort過(guò)程：
4.3.1) 選取minRun大小，之后待排序數(shù)組將被分成以minRun大小為區(qū)塊的一塊塊子數(shù)組
a) 如果數(shù)組大小為2的N次冪，則返回16（MIN_MERGE / 2）
b) 其他情況下，逐位向右位移（即除以2），直到找到介于16和32間的一個(gè)數(shù)
4.3.2) 類似于4.2.a找到初始的一組升序數(shù)列
4.3.3) 若這組區(qū)塊大小小于minRun，則將后續(xù)的數(shù)補(bǔ)足（采用binary sort插入這個(gè)數(shù)組）
4.3.4) 為后續(xù)merge各區(qū)塊作準(zhǔn)備：記錄當(dāng)前已排序的各區(qū)塊的大小
4.3.5) 對(duì)當(dāng)前的各區(qū)塊進(jìn)行merge，merge會(huì)滿足以下原則（假設(shè)X，Y，Z為相鄰的三個(gè)區(qū)塊）：
a) 只對(duì)相鄰的區(qū)塊merge
b) 若當(dāng)前區(qū)塊數(shù)僅為2，If X<=Y，將X和Y merge
b) 若當(dāng)前區(qū)塊數(shù)>=3，If X<=Y+Z，將X和Y merge，直到同時(shí)滿足X>Y+Z和Y>Z
4.3.6) 重復(fù)4.3.2 ~ 4.3.5，直到將待排序數(shù)組排序完
4.3.7) Final Merge：如果此時(shí)還有區(qū)塊未merge，則合并它們
5. Demo
這一節(jié)用一個(gè)具體的例子來(lái)演示整個(gè)算法的演進(jìn)過(guò)程：
*注意*：為了演示方便，我將TimSort中的minRun直接設(shè)置為2，否則我不能用很小的數(shù)組演示。。。同時(shí)把MIN_MERGE也改成2（默認(rèn)為32），這樣避免直接進(jìn)入binary sort。
初始數(shù)組為[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]
=> 尋找連續(xù)的降序或升序序列 (4.3.2)
[1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當(dāng)前的棧區(qū)塊為[3]
=> 進(jìn)入merge循環(huán) (4.3.5)
do not merge因?yàn)闂４笮H為1
=> 尋找連續(xù)的降序或升序序列 (4.3.2)
[1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當(dāng)前的棧區(qū)塊為[3, 5]
=> 進(jìn)入merge循環(huán) (4.3.5)
merge因?yàn)閞unLen[0]<=runLen[1]
1) gallopRight：尋找run1的第一個(gè)元素應(yīng)當(dāng)插入run0中哪個(gè)位置（”2”應(yīng)當(dāng)插入”1”之后），然后就可以忽略之前run0的元素（都比run1的第一個(gè)元素?。?nbsp;
2) gallopLeft：尋找run0的最后一個(gè)元素應(yīng)當(dāng)插入run1中哪個(gè)位置（”7”應(yīng)當(dāng)插入”8”之前），然后就可以忽略之后run1的元素（都比run0的最后一個(gè)元素大）
這樣需要排序的元素就僅剩下[5,7] [2,6]，然后進(jìn)行mergeLow
完成之后的結(jié)果：
[1,2,5,6,7,8,10,12] [4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當(dāng)前的棧區(qū)塊為[8]
退出當(dāng)前merge循環(huán)因?yàn)闂Ｖ械膮^(qū)塊僅為1
=> 尋找連續(xù)的降序或升序序列 (4.3.2)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14]
=> 入棧 (4.3.4)
當(dāng)前的棧區(qū)塊大小為[8,2]
=> 進(jìn)入merge循環(huán) (4.3.5)
do not merge因?yàn)閞unLen[0]>runLen[1]
=> 尋找連續(xù)的降序或升序序列 (4.3.2)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當(dāng)前的棧區(qū)塊為[8,2,5]
=>
do not merege run1與run2因?yàn)椴粷M足runLen[0]<=runLen[1]+runLen[2]
merge run2與run3因?yàn)閞unLen[1]<=runLen[2]
1) gallopRight：發(fā)現(xiàn)run1和run2就已經(jīng)排好序
完成之后的結(jié)果：
[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當(dāng)前入棧的區(qū)塊大小為[8,7]
退出merge循環(huán)因?yàn)閞unLen[0]>runLen[1]
=> 尋找連續(xù)的降序或升序序列 (4.3.2)
最后只剩下[14]這個(gè)元素：[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當(dāng)前入棧的區(qū)塊大小為[8,7,1]
=> 進(jìn)入merge循環(huán) (4.3.5)
merge因?yàn)閞unLen[0]<=runLen[1]+runLen[2]
因?yàn)閞unLen[0]>runLen[2]，所以將run1和run2先合并。（否則將run0和run1先合并）
1) gallopRight & 2) gallopLeft
這樣需要排序的元素剩下[13,15] [14]，然后進(jìn)行mergeHigh
完成之后的結(jié)果：
[1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16] 當(dāng)前入棧的區(qū)塊為[8,8]
=>
繼續(xù)merge因?yàn)閞unLen[0]<=runLen[1]
1) gallopRight & 2) gallopLeft
需要排序的元素剩下[5,6,7,8,10,12] [3,4,9,11]，然后進(jìn)行mergeHigh
完成之后的結(jié)果：
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 當(dāng)前入棧的區(qū)塊大小為[16]
=>
不需要final merge因?yàn)楫?dāng)前棧大小為1
=>
結(jié)束
6. 如何重現(xiàn)文章開(kāi)始提到的Exception
這一節(jié)將剝離復(fù)雜的業(yè)務(wù)邏輯，用一個(gè)最簡(jiǎn)單的例子（不修改TimSort.java內(nèi)置的各種參數(shù)）重現(xiàn)文章開(kāi)始提到的Exception。因?yàn)楸M管google出來(lái)的結(jié)果中非常多的人提到了這個(gè)Exception及解決方案，但并沒(méi)有人給出一個(gè)可以重現(xiàn)的例子和測(cè)試數(shù)據(jù)。另一方面，我也想從其他角度來(lái)加深對(duì)這個(gè)問(wèn)題的理解。
構(gòu)造測(cè)試數(shù)據(jù)的過(guò)程是個(gè)反人類的過(guò)程:( 大家不要學(xué)我。。
以下是能重現(xiàn)這個(gè)問(wèn)題的代碼：
public class ReproJava7Exception {
public static void main(String[] args) {
int[] sample = new int[]
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-2,1,0,-2,0,0,0,0};
List<Integer> list = new ArrayList<Integer>();
for (int i : sample)
list.add(i);
// use the native TimSort in JDK 7
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// miss the o1 = o2 case on purpose
return o1 > o2 ? 1 : -1;
}
});
}
}
7. Sample Code
這篇文章的所有代碼可以到github：https://github.com/Huang-Wei/understanding-timsort-java7下載。
8. References
http://en.wikipedia.org/wiki/Timsort
http://www.geneffects.com/briarskin/theory/binary/index.html
http://docs.oracle.com/javase/6/docs/api/java/util/Comparator.html#compare%28T,%20T%29
http://www.oracle.com/technetwork/java/javase/compatibility-417013.html#source
分類：01囈語(yǔ) | 標(biāo)簽： java、java7、timsort |