Pythonのソートが思うより早い理由
Wenhao Wang
Dev Intern · Leapcell

Timsort
Timsortは、マージソートと挿入ソートを組み合わせたソートアルゴリズムであり、実際には優れた効率を発揮します。Tim Petersが2002年にこのアルゴリズムを設計し、Pythonで使用されています(TimSortはPythonのlist.sortのデフォルト実装です)。このアルゴリズムは、ソートされたブロック(データのパーティション)を見つけ、各パーティションはランと呼ばれ、特定ルールに従ってこれらのランをマージします。Pythonはバージョン2.3からソートにTimsortアルゴリズムを使用しています。現在、Java SE7およびAndroidも、配列をソートするためにTimsortアルゴリズムを使用しています。
1. 操作
現実のほとんどのデータには通常、すでにソートされている部分があり、Timsortはこの機能を活用します。Timsortの入力ユニットは個々の数値ではなく、パーティションです。各パーティションは「ラン」(図1)と呼ばれます。このランのシーケンスでは、毎回1つのランを取り出してマージします。各マージは、2つのランを1つのランに結合します。各ランには少なくとも2つの要素が必要です。Timsortは各ランを昇順と降順に分割します。ランが昇順の場合、ラン内の次の要素は前の要素以上である必要があります (a[lo] <= a[lo + 1] <= a[lo + 2] <=...)
。ランが厳密な降順の場合、つまり、ラン内の前の要素が次の要素よりも大きい場合 (a[lo] > a[lo + 1] > a[lo + 2] >...)
、ラン内の要素を反転する必要があります(降順の部分は、反転されるためには「厳密に」降順である必要があることに注意してください。TimSortの重要な目標は、安定性を維持することです。>=の場合に反転を行うと、アルゴリズムは安定しなくなります)。
1.1 ランの最小長
ランはソートされたパーティションです。ランの長さは異なる場合があり、Timsortはランの長さに基づいてソート戦略を選択します。たとえば、ランの長さが特定の値よりも短い場合、挿入ソートアルゴリズムがソートに選択されます。ランの最小長(minrun)は、配列のサイズによって異なります。配列要素の数が64未満の場合、ランの最小長は配列の長さであり、Timsortは挿入ソートアルゴリズムをソートに使用します。配列要素の数が63以上の場合、大規模な配列の場合、minrunと呼ばれる数値が32〜65の範囲から選択されます。配列のサイズを最小ランサイズで割った値が2の累乗と等しいか、わずかに小さくなるようにします。このアルゴリズムは、配列のサイズの最も上位6ビットを取得し、残りのビットのいずれかが設定されている場合は1を加算し、その結果をminrunとして使用するだけです。このアルゴリズムは、配列のサイズが64未満の場合を含め、すべての場合に機能します。
1.2 ランの長さの最適化
ランの長さを最適化するとは、ランの長さがminrun未満の場合、そのようなランの長さをminrunの長さに到達させるために、適切な要素を配列から選択してランに挿入することを意味します。これにより、ほとんどのランの長さがバランスよくなるため、その後のランのマージに役立ちます。
1.3 ランのマージ
ランを分割し、ランの長さを最適化した後、次のステップはランをマージすることです。ランをマージする原理は、マージ技術で最高の効率を確保することです。Timsortアルゴリズムは、ランを見つけると、配列内のランの開始位置とランの長さをスタックに入れ、スタックに以前にプッシュされたランに従ってランをマージするかどうかを決定します。Timsortは、スタック内の非連続ランをマージしません(Timsortが非連続ランをマージしないのは、これを行うと、3つのすべてのランに共通する要素が、中央のランに関して順序が狂うためです)。
Timsortは、スタック内の2つの連続するランをマージします。X、Y、Zをスタックの一番上にある3つのランの長さを表すものとします(図2)。次の2つの条件が同時に満たされない場合、次の2つの条件が同時に満たされるまで、2つのランXとYがマージされ、その後マージが終了します:
- X>Y+Z
- Y>Z
たとえば、X<Y + Zの場合、X + Yはマージされて新しいランになり、スタックにプッシュされます。上記のステップを、2つの条件が同時に満たされるまで繰り返します。マージが終了した後、Timsortは次のランを見つけ続け、見つけた後にスタックにプッシュします。上記のステップを繰り返します。つまり、ランがスタックにプッシュされるたびに、2つのランをマージする必要があるかどうかを確認します。
1.4 ランのマージの手順
2つの隣接するランをマージするには、一時的なストレージスペースが必要です。一時的なストレージスペースのサイズは、2つのランのうち小さい方のランのサイズです。Timsortアルゴリズムは、最初に小さい方のランをこの一時的なストレージスペースにコピーし、2つのランを最初に格納していたスペースを使用して、マージされたランを格納します。
単純なマージアルゴリズムは、単純な挿入アルゴリズムを使用して、左から右または右から左の要素を順番に比較し、2つのランをマージします。効率を向上させるために、Timsortはバイナリマージソートを使用します。最初に、バイナリ検索アルゴリズムを使用して挿入位置を見つけ、挿入します。
たとえば、2つのランAとBをマージする場合、Aは小さい方のランであるとします。AとBはそれぞれすでにソートされているため、バイナリ検索では、Bの最初の要素をAに挿入する場所を見つけます(図4)。同様に、Aの最後の要素は、Bに挿入する必要がある場所で見つかります。見つけた後、この要素より後のBの要素を比較する必要はありません(図5)。この種の検索は乱数ではあまり効率的ではないかもしれませんが、他のケースでは高い効率を発揮します。
1.5 ギャロッピングモデル
上記のランと同様のマージプロセスについて説明します。詳細については、Wikipediaのギャロッピングモデルを参照してください。
2. パフォーマンス
2.1 Timsortのコアプロセス
昇順部分のバックトラッキングと降順部分のパフォーマンス低下を軽減するために、TimSortアルゴリズムは、昇順と降順の特性に従って入力を分割します。ソートの入力ユニットは、個々の数値ではなく、ブロック(パーティション)です。各パーティションは、ランと呼ばれます。これらのランシーケンスでは、毎回1つのランを取り出して、ルールに従ってマージします。各マージは、2つのランを1つのランに結合します。マージの結果はスタックに保存されます。すべてのランが消費されるまでマージが続行され、その後、スタックに残っているランが1つのランになるまでマージされます。このとき、この残りのランがソートされた結果です。
要約すると、Timsortアルゴリズムのプロセスには次のものが含まれます。
- 配列の長さが特定の値よりも短い場合は、バイナリ挿入ソートアルゴリズムを直接使用します。
- 各ランを見つけて、スタックにプッシュします。
- ルールに従ってランをマージします。
2.2 パフォーマンス分析
情報学の理論によれば、平均的なケースでは、比較ベースのソートはO(n log n)よりも速くすることはできません。Timsortアルゴリズムは、現実のほとんどのデータにはソートされた領域があるという事実を利用しているため、TimsortはO(n log n)よりも高速です。乱数の場合、利用できるソートされた領域はなく、Timsortの時間計算量はlog(n!)になります。
Timsortの時間計算量と他の比較ベースのソートアルゴリズムの比較。
空間計算量の比較。
説明: JSE 7は、クイックソートが不安定であるため、オブジェクトのソートにクイックソートを使用しませんが、Timsortは安定しています。
以下は、JSE7のTimsort実装コードからの抜粋です。これにより、Timsortの利点をよく理解できます。
安定した、適応的な、反復的なマージソート。部分的にソートされた配列で実行する場合、n lg(n)よりもはるかに少ない比較しか必要としませんが、ランダムな配列で実行する場合は、従来のマージソートに匹敵するパフォーマンスを提供します。すべての適切なマージソートと同様に、このソートは安定しており、O(n log n)時間(最悪の場合)で実行されます。最悪の場合、このソートにはn / 2オブジェクト参照の一時的なストレージスペースが必要です。最良の場合、ごくわずかな定数のスペースしか必要としません。
一般的に言って、Timsortは安定したアルゴリズムです。ソートされる配列にすでにソートされた数値がある場合、その時間計算量はn logn未満になります。他のマージソートと同様に、Timesrotは安定したソートアルゴリズムであり、最悪の場合の時間計算量はO(n log n)です。最悪の場合、Timsortアルゴリズムにはn / 2の一時的なスペースが必要であり、最良の場合、ごくわずかな一時的なストレージスペースしか必要としません。
Leapcell:Golang Webホスティングに最適なサーバーレスプラットフォーム
最後に、Golangプロジェクトをデプロイするのに最適なプラットフォームLeapcellをお勧めします。
1. 多言語サポート
- JavaScript、Python、Go、またはRustで開発します。
2. 無制限のプロジェクトを無料でデプロイ
- 使用量のみを支払います—リクエストも料金もかかりません。
3. 無敵のコスト効率
- アイドル料金なしで、従量課金制。
- 例:25ドルで、平均応答時間60msで694万リクエストをサポートします。
4. 合理化された開発者エクスペリエンス
- 楽なセットアップのための直感的なUI。
- 完全に自動化されたCI / CDパイプラインとGitOps統合。
- 実用的な洞察のためのリアルタイムのメトリックとロギング。
5. 容易なスケーラビリティと高性能
- 簡単な同時実行を処理するための自動スケーリング。
- 運用オーバーヘッドゼロ—構築に集中するだけです。
Leapcell Twitter:https://x.com/LeapcellHQ