from：http://www.lifebackup.cn/timsort-java7.html
2012年09月25日 21:57:481. 為什么寫這篇文章
這篇文章的根源是在產品中發現了一個詭異的bug：只能在產品環境下重現，在我的本地開發環境無法重現，而雙方的代碼沒有任何區別。最后用remote debug的方法找到異常所在：
Exception in thread "main" java.lang.IllegalArgumentException: Comparison
method violates its general contract!
Google了這個錯誤，是由于Java 7內置的新排序算法導致的。這才猛然想起產品的編譯環境最近升級到了Java 7。
2. 結論
在Java 6中Arrays.sort()和Collections.sort()使用的是MergeSort，而在Java 7中，內部實現換成了TimSort，其對對象間比較的實現要求更加嚴格：
Comparator的實現必須保證以下幾點（出自這兒）：
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 意味著對于任意的z：sgn(compare(x, z))==sgn(compare(y, z)) 均成立
而我們的代碼中，某個compare()實現片段是這樣的：
public int compare(ComparatorTest o1, ComparatorTest o2) {
return o1.getValue() > o2.getValue() ? 1 : -1;
}
這就違背了a)原則：假設X的value為1，Y的value也為1；那么compare(X, Y) ≠ –compare(Y, X)
PS: TimSort不僅內置在各種JDK 7的版本，也存在于Android SDK中（盡管其并沒有使用JDK 7）。
3. 解決方案
3.1) 更改內部實現：例如對于上個例子，就需要更改為
public int compare(ComparatorTest o1, ComparatorTest o2) {
return o1.getValue() == o2.getValue() ? 0 :
(o1.getValue() > o2.getValue() ? 1 : -1);
}
3.2) Java 7預留了一個接口以便于用戶繼續使用Java 6的排序算法：在啟動參數中（例如eclipse.ini）添加-Djava.util.Arrays.useLegacyMergeSort=true
3.3) 將這個IllegalArgumentException手動捕獲住（不推薦）
4. TimSort在Java 7中的實現
那么為什么Java 7會將TimSort作為排序的默認實現，甚至在某種程度上犧牲它的兼容性（在stackoverflow上有大量的問題是關于這個新異常的）呢？接下來我們不妨來看一看它的實現。
首先建議大家先讀一下這篇文章以簡要理解TimSort的思想。
4.1) 如果傳入的Comparator為空，則使用ComparableTimSort的sort實現。
4.2) 傳入的待排序數組若小于MIN_MERGE（Java實現中為32，Python實現中為64），則
a) 從數組開始處找到一組連接升序或嚴格降序（找到后翻轉）的數
b) Binary Sort：使用二分查找的方法將后續的數插入之前的已排序數組
4.3) 開始真正的TimSort過程：
4.3.1) 選取minRun大小，之后待排序數組將被分成以minRun大小為區塊的一塊塊子數組
a) 如果數組大小為2的N次冪，則返回16（MIN_MERGE / 2）
b) 其他情況下，逐位向右位移（即除以2），直到找到介于16和32間的一個數
4.3.2) 類似于4.2.a找到初始的一組升序數列
4.3.3) 若這組區塊大小小于minRun，則將后續的數補足（采用binary sort插入這個數組）
4.3.4) 為后續merge各區塊作準備：記錄當前已排序的各區塊的大小
4.3.5) 對當前的各區塊進行merge，merge會滿足以下原則（假設X，Y，Z為相鄰的三個區塊）：
a) 只對相鄰的區塊merge
b) 若當前區塊數僅為2，If X<=Y，將X和Y merge
b) 若當前區塊數>=3，If X<=Y+Z，將X和Y merge，直到同時滿足X>Y+Z和Y>Z
4.3.6) 重復4.3.2 ~ 4.3.5，直到將待排序數組排序完
4.3.7) Final Merge：如果此時還有區塊未merge，則合并它們
5. Demo
這一節用一個具體的例子來演示整個算法的演進過程：
*注意*：為了演示方便，我將TimSort中的minRun直接設置為2，否則我不能用很小的數組演示。。。同時把MIN_MERGE也改成2（默認為32），這樣避免直接進入binary sort。
初始數組為[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14]
=> 尋找連續的降序或升序序列 (4.3.2)
[1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當前的棧區塊為[3]
=> 進入merge循環 (4.3.5)
do not merge因為棧大小僅為1
=> 尋找連續的降序或升序序列 (4.3.2)
[1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當前的棧區塊為[3, 5]
=> 進入merge循環 (4.3.5)
merge因為runLen[0]<=runLen[1]
1) gallopRight：尋找run1的第一個元素應當插入run0中哪個位置（”2”應當插入”1”之后），然后就可以忽略之前run0的元素（都比run1的第一個元素小）
2) gallopLeft：尋找run0的最后一個元素應當插入run1中哪個位置（”7”應當插入”8”之前），然后就可以忽略之后run1的元素（都比run0的最后一個元素大）
這樣需要排序的元素就僅剩下[5,7] [2,6]，然后進行mergeLow
完成之后的結果：
[1,2,5,6,7,8,10,12] [4,3,9,11,13,15,16,14]
=> 入棧 (4.3.4)
當前的棧區塊為[8]
退出當前merge循環因為棧中的區塊僅為1
=> 尋找連續的降序或升序序列 (4.3.2)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14]
=> 入棧 (4.3.4)
當前的棧區塊大小為[8,2]
=> 進入merge循環 (4.3.5)
do not merge因為runLen[0]>runLen[1]
=> 尋找連續的降序或升序序列 (4.3.2)
[1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當前的棧區塊為[8,2,5]
=>
do not merege run1與run2因為不滿足runLen[0]<=runLen[1]+runLen[2]
merge run2與run3因為runLen[1]<=runLen[2]
1) gallopRight：發現run1和run2就已經排好序
完成之后的結果：
[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當前入棧的區塊大小為[8,7]
退出merge循環因為runLen[0]>runLen[1]
=> 尋找連續的降序或升序序列 (4.3.2)
最后只剩下[14]這個元素：[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14]
=> 入棧 (4.3.4)
當前入棧的區塊大小為[8,7,1]
=> 進入merge循環 (4.3.5)
merge因為runLen[0]<=runLen[1]+runLen[2]
因為runLen[0]>runLen[2]，所以將run1和run2先合并。（否則將run0和run1先合并）
1) gallopRight & 2) gallopLeft
這樣需要排序的元素剩下[13,15] [14]，然后進行mergeHigh
完成之后的結果：
[1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16] 當前入棧的區塊為[8,8]
=>
繼續merge因為runLen[0]<=runLen[1]
1) gallopRight & 2) gallopLeft
需要排序的元素剩下[5,6,7,8,10,12] [3,4,9,11]，然后進行mergeHigh
完成之后的結果：
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 當前入棧的區塊大小為[16]
=>
不需要final merge因為當前棧大小為1
=>
結束
6. 如何重現文章開始提到的Exception
這一節將剝離復雜的業務邏輯，用一個最簡單的例子（不修改TimSort.java內置的各種參數）重現文章開始提到的Exception。因為盡管google出來的結果中非常多的人提到了這個Exception及解決方案，但并沒有人給出一個可以重現的例子和測試數據。另一方面，我也想從其他角度來加深對這個問題的理解。
構造測試數據的過程是個反人類的過程:( 大家不要學我。。
以下是能重現這個問題的代碼：
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囈語 | 標簽： java、java7、timsort |