Tim sort , v 8とpythonで使われる最速のソート

あなたはどのようなアルゴリズムの背後に興味があったことがありますかArray.sort() ? 結局のところ、我々は非常に多くのソートアルゴリズムを学んだ、それぞれの利点と欠点があります.
クロムのエンジンV 8は非古典的なソートアルゴリズムを使用していることが判明Tim Sort . これは、Pythonの改善のためのPythonの主要な貢献者ティムピータースの2002年に2002年に作成されましたlist ソートパフォーマンス.それが使用するアルゴリズムの組み合わせは、実世界のデータを分析することによって決定された.最悪の場合、O(N 2)時間を実行するクイックソートの比較では、最悪の場合はO(nlog n) . そして、その最高の達成O(n) . ここでは、有名なソートアルゴリズムのテーブル、その複雑さ、安定性:

安定性を維持し、最高のパフォーマンスを達成する有効にします.ティムはリストの長さが小さいときに挿入ソートを使用することを決めました.
挿入並べ替えは、基本的には、基本的には1つの順に比較して1つのアイテムを小さくするか、それに等しいを見つけるし、この小さなアイテムの後に場所に移動する(我々は昇順でソートされていると仮定).ここではストレートフォワードGIFです.

操作を減らすために、挿入ソートの“アップグレード版”を使用することはより一般的です.バイナリーソートは、各項目の適切な場所を探しての進捗状況をスピードアップするバイナリ検索を組み合わせたものです.

それは長いリストになると、ティムソートマージソートのアイデアを使用します-小さなリストに分割“小さな”実行し、1つずつを征服し、一緒に戻ってマージ.
ここではストレートフォワードGIF :

通算する

古典的なマージソートを使用するとき、我々はしばしば固定サイズで実行するためにリストを分割するのです.ティムは異なる実行サイズを実験して、比較して、わずかにより大きな実行サイズがよりよくなるとわかりました.あなたはなぜ32と64を尋ねるかもしれません?これらの数字はどこから来ましたか.これは、Python性能測定ツールTIMが使用していたため、2サイズのデータのテスト権限しか使えなかったからです.
一方、彼はまた、実世界データには、データの多くの部分が昇順または降順でソートされていますが、ソートを必要としません.したがって、彼は“自然”サイズで実行を分割することを決めた-初期実行のサイズは、固定番号ではなく、最小限のサイズ要件を持っている-“ミンラン”.
ここでどのように分割されます.

最初の2つのアイテムを比較することによって降順フラグを設定しますfalse .

次の項目をループし、まだ昇順または“strict”の降順であるかどうかを確認します.Utilはこの順序に従っていない項目を探します.

現在、我々は昇順または「厳しい」降順のどちらかで実行をします.“strict”の順序を変更した場合、それを逆にします.ソートを安定させるために、“strict”降順部分を予約するだけです.

そして、このラン長が私の“min run”制約を満たすかどうかを確認します.
それが私の「Min Run」制約より小さいならば、Minサイズを成し遂げるために以下のアイテムを補償してください.そして、補償されたアイテムから始めている二進法並べ替えをしてください.

1つのエッジケースが“自然ラン”を持つことが起こるかもしれないことに気づくかもしれません-最後のランはmin run要件を満たさないかもしれません.これは期待され、許されます.
以下は擬似コードです:

let nremaining = list.length;
const runs = [];
const minrun = merge_compute_minrun(nremaining);

function count_run(list) {
    let descending = false;
    let n = 1;

    if (list.length === 1) return n;
    if(list[n] < list[n-1]) {
        descending = true;
    }
    n++;
    while (n < list.length && (list[n] < list[n-1] || !desending)) {
        n++;
    }
    return {
      size: n,
      descending
    };
}

do {
  const startIndex = list.length - nremaining;
  let { size, descending } = count_run();
  if (descending)
    reverse(
      list, 
      // start index
      startIndex, 
      // length to revert
      size
    );
  if (n < minrun) {
    const force = nremaining <= minrun ? nremaining : minrun;
    binarysort(
      list,
      // sort start index
      startIndex,
      // sort length
      force,
      // index to start binary search
      list.length - nremaining + size
    )
    size = force;
  }
  nremaining -= n;
  runs.push({ startIndex, size });
} while (nremaining);

マージ操作のバランスを有効にするには、実行の2カウントの権限を持つ方が良い.その結果、ティムソートはリストの長さを2、utilが64より小さくなるように分割し、それを丸めてminランを取得します.

function merge_compute_minrun(n)
{
    var r = 0;           /* becomes 1 if any 1 bits are shifted off */
    while (n >= 64) {
        r |= n & 1;
        n >>= 1;
    }
    return n + r;
}

平衡合併

古典的なマージソートは、単に隣接する2つのランをマージします.両方のソートされた配列の項目を比較するので、比較的小さい方を見つけてから、マージされたリストをメモリに格納するので、かなりのメモリスペースがかかります.ティムは、この種の不必要な廃棄物に対処する若干の方法があるかもしれないとわかります.
それで、我々が解決する必要がある最初の質問は、どの2つのランニングマージがより高いパフォーマンスを持つかです?
3つのランがあるとします
A : 1000アイテム
B : 2000アイテム
1000項目
いくつかのブログ(私は非常に明確な証拠を見つけませんでした)によると、AとCのような類似したサイズでリストを合併することはより均衡があります.しかし、問題があります-残念なことに、1つのアイテムがA、B(またはB、C、またはA、B、C)の中に存在しているなら、AとCを合併して、Bはそのアイテムの順序を変えて、安定性に影響を及ぼします.
その結果、ティムソートはまだ隣接する2つの実行を合併しますが、「固定」順序では合併しません.代わりに、それは不均衡なマージを遅らせる.
これを達成するために、それは3隣接ランの長さを比較します.もし以下の制約を満たすならば

A＞B + C

B > C

それから、基本的にBとCの実行は比較的小さい実行です.最初に小さい実行をマージすると、マージを続けるためにより大きな隣接ランニングの長さに近い高いチャンスがあります.
このプロセスの後、まだいくつかの実行が残っているならば、それは通常のマージ命令に戻るでしょう.

ギャロップモードとの融合

私たちが大規模なランニングをマージしようとするとき、彼らはすべてソートされているので、多くの時間を比較する大きなチャンスがアイテムの適切な場所を見つけることが可能です.例えば、
A : [ 0 , 2 , 4 , 6 , 8 , 10 , ..., 100 ]
B : [ 57 , 77 , 97 , ...]
B - 57の最初の項目がその最初の項目から- Aと比較し始めるならば58/2 = 29 回その場所を見つけること.そして、次の1 - 77、再び別の比較する必要があります(78 - 58)/2=10 回.
無意味な比較以外に、それらのデータを格納するためのメモリ空間も無駄にします.したがって、TIMソートはプロセスを高速化するためにGallopingを使用します.バイナリ検索と比較して、彼らの複雑さは同じです、しかし、ギャロッピングは検索開始位置から遠く離れていないデータを探すのを好みます.
これは、場所を(最初または最後の1つ)を検索を開始する必要がありますを選択して起動し、方向を検索するかどうかの出発項目が小さいか、ターゲットのデータよりも大きいを選択します.つの検索が失敗した場合は、次の時間は2つのたびに電源を入れることによって遠い場所を試してみる.
例えば、[ 7 ]から検索を開始し、A [ 7 ]が目標データよりも小さい場合、[ 9 ]を比較し、次の[ 11 ]、A [ 15 ]、A [ 23 ]、A [ 35 ]…を比較します.util 1つのターゲットデータより大きいか、等しいかを検出します.より大きなものが[ 35 ]であると仮定してください、そして、それは目標データが[ 23 ]とa [ 35 ]の間のどこかに属しなければならないということを知っていることができました.
一度この荒い範囲を得て、それはEACT位置を見つけるために、バイナリ検索に切り替えます.
以下は擬似コードです:

function gallop_left(
   key, // the data to merge
   a, // the run to merge to 
   startIndex
)
{
    let lastofs = 0; // starting point for binary search
    let ofs = 1;  // end point for binary search
    const n = a.length;
    if(a[hint] < key) {
        // compare from left to right
        const maxofs = n - hint;
        while (ofs < maxofs && a[ofs] < key) {
          lastofs = ofs;
          ofs = (ofs << 1) + 1;
        }
        if (ofs > maxofs) ofs = maxofs;
        lastofs += hint;
        ofs += hint;
    } else {
        // compare from right to left
        const maxofs = hint + 1;
        while (ofs < maxofs && a[hint - ofs] < key) {
            lastofs = ofs;
            ofs = (ofs << 1) + 1;
        }
        if (ofs > maxofs) ofs = maxofs;
        let tmp = lastofs;
        lastofs = hint - ofs;
        ofs = hint - tmp;
    }

    // do binary search at the end
    ++lastofs;
    while (lastofs < ofs) {
        let m = lastofs + ((ofs - lastofs) >> 1);
        if(a[m] < key) lastofs = m+1;
        else ofs = m;
    }
    return ofs; // return the found index
}

ギャロップモードを使うとき

彼らがちょうどマージを始めるとき、2つの走力の間に大きなギャップがありそうです.例えば、次の2点があります.
A : [ 0 , 2 , 4 , 6 , 8 , 10 , ..., 100 ]
B : [ 57 , 77 , 97 , ...]
だからここで使用できるgallop_left(b[0], a, 0) (左側のポイントから始まる)、すぐにどこに位置するかb[0] にa . 使用gallop_right(a[a.length - 1], b, b.length - 1) (右側のポイントから始まる)a[0] にb , それで、比較的に比較とマージを必要とするデータのサイズを短くすることができます.gallop_left and gallop_right ほとんど同じことをするだけでいくつかの小さなエッジの手持ちがあります.
以下は擬似コードです:

function merge(ms /* MergeState */, a, b) {
    let k = gallop_right(b[0], a, 0);
    if (k < 0) throw -1;
    let merged = a.splice(0, k);
    if (a.length == 0) 
      return merged.concat(b);
    else
      merged.push(b.shift());

    let nb = gallop_left(a[a.length-1], b, b.length - 1);
    if (nb <= 0) throw nb;
    const lastPart = b.splice(nb);
    lastPart.unshift(a.pop());

    if (a.length <= nb)
        merged = merged.concat(merge_lo(ms, a, b));
    else
        merged = merged.concat(merge_hi(ms, a, b));
    return merged.concat(lastPart);
}

ギャロップモードはクールですが、実行中の大きなギャップがあるときにだけうまく動作し、そうでなければそれはパフォーマンスを低下されます.したがって、TIMソートは、Gallopモードに入るためにいくつかの制約を導入しました.
Pythonでは、データが7回比較され、まだまだその場所を見つけるときにGallopモードに入ります.そして、最も興味深いことは、マージがギャロップモードに入り続けるのを見つけたなら、この制約はより低くなるでしょう.そして、それがギャロッピングを引き起こさなかったならば、少し抑制してください.これは格闘ゲームをプレイのような感じ-動きの深刻なことは、ダメージを拡大し、1つの動きが右ではない場合は、余分な損害賠償をリセットします.
以下は擬似コードです:

const MIN_GALLOP = 7;

function merge_lo(
  ms, // MergeState
  a, // the shorter run
  b // the longer run
) {
      let min_gallop = ms.min_gallop;
    let merged = [];

    for (;;) {
        let acount = 0;          /* # of times A won in a row */
        let bcount = 0;          /* # of times B won in a row */

        // do sequential comparing first, util it fulfils the galloping constrain
        do {
            if (b[0] < a[0]) {
                merged.push(b.shift());
                ++bcount;
                acount = 0;
                if (b.length == 0) return merged.concat(a);
            } else {
                merged.push(a.shift());
                ++acount;
                bcount = 0;
                if (a.length == 0) return merged.concat(b);
            }
        } while ((acount || bcount) >= min_gallop))

        // galloping and merging
        ++min_gallop;
        do {
            ms.min_gallop = min_gallop -= min_gallop > 1;
            let k = gallop_right(b[0], a, 0);
            acount = k;
            if (k) {
                if (k < 0) return -1;
                merged = merged.concat(a.splice(0, k));
                if (a.length == 0) return merged.concat(b);
            }
            merged.push(b.shift());
            if (b.length == 0) return merged.concat(a);

            k = gallop_left(a[0], b, 0);
            bcount = k;
            if (k) {
                if (k < 0) return -1;
                merged = merged.concat(b.splice(0, k));
                if (b.length == 0) return merged.concat(a);
            }
              merged.push(a.shift());
            if (a.length == 0) return merged.concat(b);
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ms.min_gallop = ++min_gallop;
    }
    return merged;
 }

もう一つの機能がありますmerge_hi 実は.それはとても似ているからmerge_lo , それで、私はそれをスキップします.

それで

さて、V 8(私は真剣にソースコードを読む気分がありません…)によるとhere , リストがPythonのように32 - 64分より大きいならば、それはTIMソートを始めません.リストサイズが100より大きいときのみ起動します512 , これはほとんどの場合、私たちはTimeSortの代わりにバイナリソートを入力するだけです.
ティムおじさんが考えている方法と彼が選んだ解決策は、私にとってとても魅力的ですが、Cコードではありません😂. 私は、あなたがあなたが意味するものを得ると思います.あなたは読書をお楽しみください.

参考文献

Tim Sort - ウィキペディア

Timsort — the fastest sorting algorithm you’ve never heard of - ブランドン

Python Timsort doc - Pythonorg

Python source code - listobject.c