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がマージされ、その後マージが終了します:

1. X>Y+Z
2. 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アルゴリズムのプロセスには次のものが含まれます。

1. 配列の長さが特定の値よりも短い場合は、バイナリ挿入ソートアルゴリズムを直接使用します。
2. 各ランを見つけて、スタックにプッシュします。
3. ルールに従ってランをマージします。

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