バブルソートに加えて、Python の組み込みソートアルゴリズムをご存知ですか?

プログラミング アルゴリズムに関して、多くの読者が学校で最初に学ぶのはバブル ソートかもしれませんが、Python の組み込みソート アルゴリズム list.sort() の原理を本当にご存知ですか? これは、時間計算量が O(n log n) の高速で安定したソート アルゴリズム Timsort を使用します。このアルゴリズムの目的は、大規模な実データを処理することです。

Timsort は、実際のデータに対して非常に効率的なソート アルゴリズムです。 Tim Peters は 2001 年に Python プログラミング言語用に Timsort を作成しました。 Timsort は、まずソートしようとしているリストを分析し、その分析に基づいて適切なソリューションを選択します。

Timsort は発明されて以来、Python、Java、Android プラットフォーム、GNU Octave のデフォルトのソート アルゴリズムとなっています。

画像ソース: http://bigocheatsheet.com/

Timsort のソート時間は Mergesort と似ており、他のほとんどのソート アルゴリズムよりも高速です。 Timsort は、実際には挿入ソートとマージソートの手法を借用しています。その具体的な処理については、後ほど詳しく説明します。

Peters 氏は、実際のデータ セットに存在する「自然実行」と呼ばれる多数の順序付けられた要素を利用するために Timsort を設計しました。要約すると、Timsort は最初にすべてのデータを走査し、データ内のソートされたパーティションを見つけます。各パーティションは実行と呼ばれ、次にルールに従ってこれらの実行を 1 つにマージします。

配列の要素数が 64 未満です。

ソートする配列の要素数が 64 未満の場合、Timsort は挿入ソートを実行します。挿入ソートは、小さなリストに対して最も効率的な単純なソートです。大きなリストでは遅くなりますが、小さなリストでは速くなります。挿入ソートの考え方は次のとおりです。

• 要素を一つずつ表示する
• 正しい位置に要素を挿入してソートされたリストを作成します

次のトレーステーブルは、挿入ソートがリスト[34, 10, 64, 51, 32, 21]をどのようにソートするかを示しています。

この例では、左から右へのソートを開始します。太字の数字は、新しくソートされたサブ配列を表します。元の配列の各要素をソートする際に、ソートされたサブ配列を右から左に比較し、適切な位置に挿入します。挿入ソートを説明するために動画を使用します。

自然に順序付けられたブロック: 実行

リストが 64 要素より大きい場合、Timsort アルゴリズムは最初にリストを走査し、「厳密に」昇順または降順の部分を探します (実行)。セクションが減少している場合、Timsort はそのセクションを反転します。したがって、run が減少している場合は、次のようになります (run は太字で表示されます)。

減少がない場合は、次のようになります。

minrun のサイズは配列のサイズに基づいて決定されます。 Timsort アルゴリズムは、ランダム配列内のほとんどの実行が minruns になるようにこれを選択します。実行の長さ N が 2 の倍数と等しいかわずかに小さい場合、2 つの配列を結合する方が効率的です。 Timsort は、minrun が 2 の倍数と等しいか、わずかに小さいことを保証するために minrun を選択します。

アルゴリズムは minrun の範囲を 32 ～ 64 に選択します。 minrun で割ると、元の配列の長さは 2 の倍数と等しくなるか、わずかに小さくなります。

実行の長さが minrun より短い場合は、minrun から実行の長さを引いた値が計算されます。実行後に新しい要素を run (minrun - run) の外側に配置し、挿入ソートを実行して、長さが minrun と同じ新しい実行を作成できます。

minrun が 63 で、run の長さが 33 の場合、63 - 33 = 30 個の新しい要素を取得できます。そして、これらの30個の新しい要素はrunの末尾に新しい要素として追加されるため、runの34番目の要素であるrun[33]には30個の子要素があります。 ***長さ 63 の新しい実行を作成するには、最後の 30 要素に対して挿入ソートのみが必要です。

この部分が完了すると、リスト内に並べ替えられた実行セットが作成されます。

マージ

Timsort は、実行をマージするためにマージ ソートを実行する必要があり、マージ ソートの実行中に安定性とバランスが維持されるようにする必要があります。安定性を維持するために、等しい値を持つ 2 つの要素は交換しないでください。これにより、リスト内の元の位置が維持されるだけでなく、アルゴリズムも高速化されます。

Timsort が実行を見つけると、それらはスタックに追加されます。単純なスタックは次のようになります。

皿が積み重ねられているところを想像してください。皿を下から取ることはできません。上から取る必要があります。積み重ねた場合も同様です。

異なる実行をマージする場合、Timsort は 2 つの競合する要件のバランスを取ろうとします。一方では、後で出現する可能性のあるパターンを活用するために、マージをできるだけ遅らせたいと考えています。しかし、メモリ階層でまだ高いランクにある、先ほど発見した実行を活用するために、できるだけ早くマージすることを希望します。また、マージされていない実行を記憶するとメモリが消費され、スタックのサイズが固定されているため、マージを「あまり」遅らせることもできません。

妥協案を見つけるために、Timsort はスタック上の最新の 3 つの項目を追跡し、それらのスタック項目に当てはまる必要がある 2 つのルールを作成します。

• A > B + C
• B > C

ここで、A、B、C はスタック内の最新の 3 つの項目です。

ティム・ピーターズ自身の言葉：

通常、長さの異なる隣接するランを結合することは困難です。さらに難しいのは、安定性を維持しなければならないことです。この問題を解決するために、Timsort は一時メモリを設定します。 2 つの実行 (runA と runB を同時に呼び出す) のうち小さい方をこの一時メモリに配置します。

GALLOPING（ギャロッピングモード）

Timsort が A と B をマージすると、1 回の実行が複数回連続して「勝利」したことに気付きます。実行 A の値が実行 B の値よりも大幅に小さい場合、実行 A は元の位置に戻ります。これら 2 つの実行をマージすると、膨大な作業量になり、何の結果も得られません。

通常、データには事前に設定された内部構造があります。 Timsort は、実行 A の値が実行 B の値よりもほとんど低い場合、A の値は B よりも低くなる可能性が高いと想定します。

その後、ティムソートはギャロップモードに入ります。 A[0]とB[0]をチェックする代わりに、TimsortはA[0]内でのB[0]の適切な位置をバイナリ検索で探します。このようにして、Timsort はセクション A 全体を所定の位置に移動できます。次に、TimsortはBでA[0]の適切な場所を検索します。その後、Timsort は B 全体を直ちに所定の位置に移動します。

TimsortはB[0]（値は5）をチェックし、バイナリ検索を使用してA内の正しい位置を見つけます。

現在、B[0]はAのリストの最後にあり、TimsortはBの正しい位置にA[0]（1）があるかどうかをチェックし、1の位置を確認します。この数字は B の前にあります。これで、B は A の後ろにあり、A は B の前にあることがわかります。

B[0]がAの先頭に非常に近い位置にある場合（またはその逆）、この操作は不要です。 Timsort もこれに気づき、連続する A または B の数を増やすことで、ギャロップ モードに入るしきい値を上げます。ギャロッピング モードが意味をなす場合、Timsort を使用すると、そのモードに再び入るのが簡単になります。

簡単に言うと、Timsort は次の 2 つの非常に優れた機能を備えています。

• 内部構造があらかじめ設定されている配列はパフォーマンスが良好です
• 安定した選別を維持できる

これまでは、安定したソートを実現するために、リスト内の項目を整数に圧縮し、タプルの配列にソートする必要がありました。

コード

以下のソース コードは、私と Nanda Javarma の作業に基づいています。ソースコードは完全ではなく、Python の公式 sort() ソースコードとも似ていません。これは私が実装した単純化された Timsort ですが、これにより Timsort の全体像を把握することができます。さらに、Python に組み込まれている Timsort アルゴリズムは C で正式に実装されているため、パフォーマンスが向上します。

Timsort のオリジナル ソース コード:

https://github.com/python/cpython/blob/master/Objects/listobject.c をご覧ください。

 # このコードに基づいています https://gist.github.com/nandajavarma/a3a6b62f34e74ec4c31674934327bbd3
 #ブランドン・スケリット
# https://skerritt.tech 
 
 def binary_search(配列、項目、開始、終了):
    開始== 終了の場合:
        the_array[start] > itemの場合:
            戻る 開始
        それ以外：
            開始 + 1 を返す
    開始>終了の場合:
        戻る 開始
 
中間=ラウンド((開始 + 終了) / 2) 
 
    配列[mid] <  アイテム：  
        バイナリ検索(配列、項目、中間 + 1、終了)を返します
 
    elif the_array[mid] >項目:
        binary_search(the_array, item, start, mid - 1) を返します
 
    それ以外：
        戻る途中
 
 「」
配列のサイズが小さい場合や、
 「実行」のサイズが小さい
「」
 def inserting_sort(配列):
 l = len (配列)
    範囲(1, l)内のインデックスの場合:
値= the_array [インデックス]
 pos = binary_search (配列、値、0、インデックス - 1)
 the_array the_array = the_array[:pos] + [値] + the_array[pos:index] + the_array[index+1:]
    配列を返す
 
 def merge(左、右):
    「2つのソートされたリストを受け取り、それらを比較して1つのソートされたリストを返します。
    要素を 1 つずつ選択します。
    [1、2、3、4、5、6]
    「」
    残っていない場合:
        右に戻る
    正しくない場合:
        左に戻る
    左[0]の場合<  右[0]:
        [left[0]] + merge(left[1:], right) を返す
    [right[0]] + merge(left, right[1:]) を返す
 
 def timsort(配列):
    実行、 sorted_runs = []、[]
 len長さ= len(配列)
 new_run = [the_array[0]] 
 
    # 1から配列の長さまでの範囲のすべてのiについて
    iが範囲(1, 長さ)内にある場合:
        # i がリストの末尾にある場合
        i == 長さ - 1 の場合:
            new_run.append(配列[i])
            実行します。追加(new_run)
            壊す
        # 配列のi番目の要素がその前の要素より小さい場合
        配列[i] <  配列[i-1]:
            # new_run が None (NULL) に設定されている場合
            new_runでない場合は:
                実行します。追加([the_array[i]])
                new_run.append(配列[i])
            それ以外：
                実行します。追加(new_run)
新しい実行= []
        # そうでない場合、等しいかそれ以上の場合
        それ以外：
            new_run.append(配列[i]) 
 
    # 実行中のすべての項目に対して、挿入ソートを使用して追加します
    実行中のアイテムの場合:
        sorted_runs.append(挿入ソート(アイテム)) 
 
    # sorted_runs 内の各実行をマージします
ソートされた配列= []
    sorted_runs 内の実行の場合:
 sorted_array = merge (sorted_array, 実行) 
 
    print(ソートされた配列) 
 
 timsort([2, 3, 1, 5, 6, 7])

Timsort は実際には Python に組み込まれているため、このコードは概念的な説明としてのみ機能します。 Timsort を使用するには、Python で次のように記述するだけです。

リスト.ソート()

または：

ソート済み(リスト)

Timsort がどのように動作するかを把握し、理解したい場合は、ぜひ自分で実装してみることをお勧めします。

オリジナルリンク:

https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399

[この記事は51CTOコラム「Machine Heart」、WeChatパブリックアカウント「Machine Heart（id:almosthuman2014）」によるオリジナル翻訳です]

この著者の他の記事を読むにはここをクリックしてください