のMarc Sendra martorellによる写真Timsort：現実の世界のために構築された非常に高速でO（n log n）、安定したソートアルゴリズム—学界では構築されていません。
更新された記事を表示するにはここをクリックしてください:
Timsortは、現実世界のデータに対して効率的であり、学術研究室で作成されていないソートアルゴリズムです。 ティム-ピーターズは2001年にPythonプログラミング言語のTimsortを作成しました。 Timsortは最初にソートしようとしているリストを分析し、リストの分析に基づいてアプローチを選択します。
アルゴリズムが発明されて以来、Python、Java、Androidプラットフォーム、GNU Octaveではデフォルトのソートアルゴリズムとして使用されてきました。Timsortの大きなO表記はO（n log n）です。 Big O記法について学ぶには、これを読んでください。
Timsortのソート時間はMergesortと同じで、これはあなたが知っているかもしれない他の種類のほとんどよりも高速です。 すぐにわかるように、Timsortは実際には挿入ソートとMergesortを使用します。
Petersは、ほとんどの実世界のデータセットに存在する既に順序付けられた要素を使用するようにTimsortを設計しました。 これは、これらの既に順序付けられた要素を”自然な実行”と呼びます。 これは、要素を実行に収集し、同時にそれらの実行を1つにマージするデータを反復処理します。
配列には64個未満の要素があります
ソートしようとしている配列に64個未満の要素がある場合、Timsortは挿入ソートを実行します。
挿入ソートは、小さなリストで最も効果的な単純なソートです。 大きなリストでは非常に遅いですが、小さなリストでは非常に高速です。 挿入ソートの考え方は次のとおりです:
- 要素を1つずつ見てください
- 正しい場所に要素を挿入してソートされたリストを構築します
挿入ソートがリストをソートする方法を示すトレーステー
この例では、新しくソートされた要素を配列の先頭から始まる新しいサブ配列に挿入しています。
ここに挿入ソートを示すgifがあります:
実行についての詳細
リストがアルゴリズムよりも64要素より大きい場合は、厳密に増加または減少している部分を探してリ 部分が減少している場合は、その部分を逆にします。
だから、実行が減少している場合、それは次のようになります（実行は太字で表示されます）:
減少しない場合は、次のようになります:
minrunは、配列のサイズに基づいて決定されるサイズです。 アルゴリズムは、ランダム配列内のほとんどの実行が長さがminrunになるように選択します。 2つの配列をマージする方が、実行回数が2の累乗またはそれよりわずかに少ない場合に効率的です。 Timsortは、minrunが2のべき乗以下であることを確認することによって、この効率を確保しようとするminrunを選択します。
アルゴリズムは、32から64までの範囲のminrunを選択します。 元の配列の長さをminrunで除算したときに、2のべき乗に等しいか、またはわずかに小さいようにminrunを選択します。minrunを使用して、元の配列の長さをminrunで除
実行の長さがminrunより小さい場合、minrunから離れた実行の長さを計算します。 この新しい番号を使用して、実行の前にその多くの項目を取得し、挿入ソートを実行して新しい実行を作成します。したがって、minrunが63で、実行の長さが33の場合、63-33=30となります。 次に、実行の終わりの前から30個の要素を取得するので、これは実行から30個の項目であり、挿入ソートを実行して新しい実行を作成します。
この部分が完了したら、リストにソートされた実行の束があるはずです。
Timsortは、実行をマージするためにmergesortを実行するようになりました。 ただし、Timsortは、マージソート中に安定性とマージバランスを維持することを確認します。
安定性を維持するために、等しい値の2つの数を交換すべきではありません。 これは、リスト内の元の位置を保持するだけでなく、アルゴリズムを高速化することを可能にします。 私たちはすぐにマージ残高について説明します。
Timsortは実行を検出すると、それらをスタックに追加します。 単純なスタックは次のようになります:
プレートの積み重ねを想像してみてください。 あなたは下からプレートを取ることができないので、上からそれらを取る必要があります。 スタックについても同じことが言えます。
Timsortは、mergesortが実行されるときに、競合する二つのニーズのバランスを取ろうとします。 一方で、後で発生する可能性のあるパターンを利用するために、マージをできるだけ長く遅らせたいと考えています。 しかし、見つかった実行がまだメモリ階層の上位にある実行を悪用するために、できるだけ早くマージを行うことをさらに望んでいます。 また、マージされていない実行を記憶するためにメモリを消費し、スタックのサイズが固定されているため、マージを”長すぎる”遅らせることはできません。
この妥協点を確実にするために、Timsortはスタック上の最新の三つの項目を追跡し、それらの項目に当てはまる必要がある二つの法則を作成します。
1。 A>B+C
2. B>C
ここで、A、B、Cはスタック上の最新の三つの項目です。
ティム-ピーターズ自身の言葉で:
良い妥協であることが判明したのは、スタックエントリに二つの不変量を維持しています。A、B、Cは、まだマージされていない三つの右端のスライスの長さです
通常、異なる長さの隣接するランをマージするのは難しいです。 それをさらに困難にするのは、安定性を維持しなければならないということです。 これを回避するために、Timsortは一時的なメモリを確保します。 これは、2つの実行のうち小さいもの（実行AとBの両方を呼び出す）をその一時メモリに配置します。
TimsortがaとBをマージしている間、1回の実行が何度も連続して「勝利」していることに気付きます。 実行Aが実行Bよりも完全に小さい数値で構成されていることが判明した場合、実行Aは元の場所に戻ります。 二つの実行をマージするには、何も達成しないために多くの作業が必要です。
多くの場合、データはいくつかの既存の内部構造を持っています。 Timsortは、実行Aの値の多くが実行Bの値よりも低い場合、Aは引き続きBよりも小さい値を持つ可能性が高いと想定しています。
Timsortはギャロッピングモードに入ります。 AとBを互いにチェックする代わりに、Timsortはa内のbの適切な位置のバイナリ検索を実行します。 その後、TimsortはB内のaの適切な場所を検索します。Timsortは、Bのセクション全体を一度に移動し、所定の位置に移動します。
これを実際に見てみましょう。 TimsortはB（5）をチェックし、バイナリ検索を使用してAの正しい場所を探します。
さて、BはAのリストの後ろに属します。TimsortはBの正しい場所にA（1）をチェッ 私たちは今、Bがaの終わりに属し、AがBの始まりに属していることを知っています。
Bの適切な位置がAの先頭に非常に近い（またはその逆）場合、この操作は価値がありません。 それが報われていない場合ので、ギャロップモードはすぐに終了します。 さらに、Timsortはメモを取り、入力するために必要な連続したAのみまたはBのみの勝利の数を増やすことにより、後でギャロップモードに入ることが困難に ギャロップモードがオフに支払っている場合は、Timsortは、それが簡単に再入力することができます。
要するに、Timsortは2つのことを信じられないほどうまくやっています:
- 既存の内部構造を持つ配列での優れたパフォーマンス
- 安定したソートを維持できる
以前は、安定したソートを達成するためには、リスト内の項目を整数で圧縮し、タプルの配列としてソートする必要がありました。コード
コード
コードに興味がない場合は、この部分をスキップして自由に感じてください。 このセクションの下にいくつかのより多くの情報があります。
以下のソースコードは、mineとNanda Javarmaの仕事に基づいています。 ソースコードは完全ではなく、Pythonの公式のsorted()ソースコードにも似ていません。 これは私がTimsortの一般的な感触を得るために実装された単なる愚かなTimsortです。 Timsortの元のソースコードをすべての栄光で見たい場合は、ここでチェックしてください。 Timsortはpythonではなくcで公式に実装されています。
Timsortは実際にはPythonに組み込まれているため、このコードは説明者としてのみ機能します。 Timsortを使用するには、次のように記述します:
list.sort()
または
sorted(list)
あなたがTimsortがどのように動作するかを習得し、それの感触を得たい場合は、私は非常にあなたがそれを自分で実装しようとすることをお勧めします！
この記事は、ここにあるティム-ピーターズのTimsortへのオリジナルの紹介に基づいています。