<スパン 1. 概要

少し前にCollections.sort()を使っていると例外が発生し、相棒の@zhuidawuguiとトラブルシューティングした結果、JDK7でソートの実装がTimSortに変更されたことが原因だとわかり、この素晴らしいアルゴリズムについてさらに調べました。

<スパン 2. 背景

なぜこの例外を調べているかというと、先日、オンラインサーバーで以下のような例外が時々ログに残っているのを発見したからです。

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;
    }
});

JDK7 のソートメソッドの実装では、compare メソッドは 2 つの値が等しい場合は 0 を、そうでない場合は 0 を返す必要があります。 かもしれない はソート時にエラーを投げますが、JDK6にはこの制限がありません。

この問題はテスト時には発生せず、オンラインでも小さな確率で再発する程度ですが、この問題を安定して再発させるにはどうしたらよいでしょうか。ソースコードを見ると、例外を投げるものは、単に不可解なものです。

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

この混乱を解くために、Timsortのjava実装のコードを解析してみました。

<スパン

<スパン 3. Timsortの概要

TimSort は、マージソートと挿入ソートを組み合わせ、いくつかの最適化を行ったものである。部分的にソートされた配列の場合、時間計算量は O(n log(n)) を大きく下回り、好ましくは O(n) までです。また、ランダムにソートされた配列の場合、時間計算量は O(nlog(n)) であり、平均時間計算量は O(nlog(n)) となります。

その全体像は次のようなものである。

1. 配列を繰り返し処理し，昇順または降順のフラグメントに分割します（降順のフラグメントの場合は，降順のフラグメントを反転して昇順にします）．
2. 配列からRunTaskを取り出し、このRunTaskをスタックします。
3. スタック上で互いに隣接する2つのRunTaskを取り出し、マージソートを行い、その結果を再びスタックします。
4. (2)(3)を全てのデータを処理するまで繰り返す。

この記事ではTimsortの全体的なアイデアについてあまり詳しく説明しませんが、興味のある方のために [Timsortを理解する、パート1：適応型マージソート（Adaptive Mergesort

<スパン 4. ティムソートのサブサンプション

Timsortのマージに注目してみましょう。の配列がある場合、通常のマージソートに比べてマージ処理が多少最適化されます。

<スパン 1. セグメントAとセグメントBは、以下のアドレスで物理的に隣接していることに注意してください。

2. セグメント A の始点は base1、残りの要素数は len1 であり、セグメント B の始点は base2、残りの要素数は len2 であるとします。セグメント A で B[base2] 以下の値を持つセグメントをマージ結果の始点とし、セグメント A の終点値 a[base1 + len1 - 1] を取り、B セグメントで分岐し、B セグメントで a[base1 + len1 - 1] 以上の値を持つセグメントを結果の終点として使用します。

もっと具体的に言うと、ここでマージするデータを"dit"して、途中のデータだけをマージするのです。

3. その後、インターセプト後のBセグメントのサイズのtmp配列を作成し、Bセグメントの残りのデータをコピーする必要があります。このデータは、マージ時に上書きされるためです。

このプログラムは、マージするデータへのポインタであるcorsor1とcorsor2を、最初はAセグメントとtmpセグメントの末尾に記録します。また、マージされた配列の dest へのポインタを、元の B セグメントの末尾に記録します。

destポインタを生成すると、cursor-,dest-で、セグメントAのcursor1が指すデータをセグメントBの末尾に直接コピーすることができます。なぜなら、前のステップ(2)で既にarr[cursor1]>arr[dest]が保証されているからです。

<スパン 4. サブサンプションソートを行うために、ここでは各サンプション比較で、Aセグメントとtmpセグメント間の"勝ち（お互いより大きい）"の数を記録し、比較が失敗（お互いより小さい）した場合は勝ち数をクリアすることになります。N回連続で勝利したセグメントがあると、別の最適化戦略が起動されます。

5. N連勝の場合、セグメントAのデータの方がセグメントBよりも平均的に大きいと仮定できます。このとき、tmp[cursor2]の値を用いて、A[base0]からA[cursor1]のインデックスkでtmp[cursor2]より小さいものを最初に見つけ、A[k+1]からA[cursor1]へのデータは直接A[dest-len, dest]に移動させることになります。

例のデータ、tmp[cursor2]=8の場合、A配列の8より小さい最初のインデックス（-1）を見つけ、その後、cursor1とdestのポインタを2ポジション左にずらして、A[dest-1, dest]に入力します。

6. cursor1>=0であれば、次にcurosr1が指すデータで再びtmp配列を探し、ここでcursor1は既に-1なので、ループは終了します。

7. 最後に、tmpの残りのデータをA配列の残りの位置にコピーして、ループを終了します。

<スパン 5. 例外が発生した場合のTimsortのサブサンプション

ここで実装したcompare(obj o1,obj o2)が次のようなものだったとする。

public int compare(Integer o1, Integer o2) {
    return o1>o2?1:-1;
}

<スパン 1. まだA,Bのセグメントに分かれています。

<スパン 2. "pinch"では、いくつかの変更があり、プログラムが比較(B[base2],A[base1])すると-1を返し、Aの左側には切り取るべき2つの"5s"が残っています。

<スパン

<スパン 3. <スパン 次は、通常のマージ処理です。

<スパン <スパン

<スパン 4. <スパン ここで再び、"win" >Nロジックが発動します

<スパン <スパン <スパン

<スパン <スパン <スパン 5. A[base1,cursor1] から tmp[cursor2] よりも小さい要素を見つけ、それらをコピーし、cursor1 と dest を左に2箇所シフトする。

<スパン <スパン <スパン <スパン

<スパン <スパン <スパン 6. <スパン このとき、A[cursor1]でtmpを再度調べます。tmpのデータはすべてA配列に移動し、cursor2, destは4ビット左にシフトします。tmp2の残りの要素数（len2）は0です。

<スパン <スパン <スパン <スパン <スパン

注目!

ルックアップのステップ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メソッドはその一般契約に違反する"例外がスローされます。この問題は、"win N times"最適化がトリガーされ、(A[base1]==A[base1+x])&&（A[base1+x]==B[base2]）といったデータ配列があると再現されるのです。この他にもいくつかのトリガー条件があるはずですが、限られた労力の中で、掘り下げることはしません。

<スパン 6. 参考資料

Java 7におけるTimSort TimSortのOpenJDKソースコード読み込み (http://blog.csdn.net/on_1y/article/details/30109975)