ティムソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』
ティムソート
クラス ソートアルゴリズム
データ構造 配列
最悪計算時間 [1][2]
最良計算時間 [3]
平均計算時間
最悪空間計算量

ティムソート (Timsort) は2002年にPythonで TimPetersによって実装された安定ソートアルゴリズムの一種。マージソートと挿入ソートから派生しており、実世界の多くの種類のデータで適切に機能するように設計されている。

このアルゴリズムは、すでに整列されているデータのサブシーケンスを見つけ、それらを使用して残りをより効率的にソートします。これは、特定の基準が満たされるまで並びをマージすることによって行われます。 ティムソートは、バージョン2.3以降のPythonの標準的な並べ替えアルゴリズムで、Java SE 7 [4]、Androidプラットフォーム [5]、GNU Octave [6]、V8 [7]、Swift [8]、Rust [9] においても非プリミティブ型の配列のソートアルゴリズムとして採用されています。

ティムソートは、PeterMcIlroyの1993年の論文「Optimistic Sorting and Information Theoretic Complexity」の手法を使用しています。 [10]

手法[編集]

ティムソートでは、ほとんどの実世界のデータに最初から存在する、連続した要素の自然な並びを利用するように設計されました。要素を収集しながらデータを順番に読み取っていくと同時に、それらの並びをスタックに配置します。スタックの最上位の並びがマージ基準に一致する場合は常に、それらはマージされます。これは、すべてのデータがトラバースされるまで続きます。次に、すべての並びが一度に2つマージされ、ソートされた並びは1つだけ残ります。 （従来のマージソートで行われるように）固定サイズのサブリストをマージする代わりに順序付けられた並びをマージする利点は、リスト全体をソートするために必要な比較の総数が減ることです。

各並びには、入力のサイズに基づく最小サイズがあり、アルゴリズムの開始時に定義されます。並びがこの最小並びサイズよりも小さい場合、挿入ソートを使用して、最小並びサイズに達するまで並びに要素を追加します。

マージ基準[編集]

要素の並びはスタックに挿入されます。 |Z| ≤ |Y| + |X| の場合、次にXとYがマージされ、スタック上で置き換えられます。このようにして、すべての並びがi. |Z| > |Y| + |X| i. |Z| > |Y| + |X|およびii. |Y| > |X| ii. |Y| > |X| 。

ティムソートは、安定ソートアルゴリズムであり（同じキーを持つ要素の順序が保持されます）、バランスの取れたマージ（マージにより、同様のサイズの並びがマージされます）の実行に努めます。

並べ替えの安定性を実現するために、連続する並びのみがマージされます。 2つの連続しない並びの間に、並び内に同じキーを持つ要素が存在する可能性があります。これらの2つの並びをマージすると、等しいキーの順序が変更されます。この状況の例（[]は順序付けられた並びです）：[1 2 2] 1 4 2 [0 1 2]

バランスの取れたマージを追求するために、ティムソートは、スタックの最上位で3つの並び、 X 、 Y 、 Zを考慮し、不変条件を維持します。

  1. |Z| > |Y| + |X|
  2. |Y| > |X|[11]

これらの不変条件のいずれかに違反した場合、 YはXまたはZの小さい方とマージされ、不変条件が再度チェックされます。不変条件が保持されると、データ内の新しい並びの検索を開始できます。 [12]これらの不変条件は、バランスのためのマージの遅延、キャッシュメモリでの並びの新たな発生の活用、およびマージの決定を比較的簡単にすることの間の妥協点を維持しながら、マージをほぼバランスの取れたものとして維持します。

マージの空間オーバーヘッド[編集]

マージするために、ティムソートは小さい方の配列（この図ではX）の要素を一時メモリにコピーし、要素を最終的な順序で並べ替えて、XとYの結合されたスペースに入力します。

元のマージソートの実装はインプレースではなく、N（データサイズ）のスペースオーバーヘッドがあります。インプレースマージソートの実装は存在しますが、時間のオーバーヘッドが高くなります。落としどころとして、ティムソートでは、Nよりも時間オーバーヘッドと空間オーバーヘッドが小さいマージソートを実行します。

最初に、ティムソートは二分探索を実行して、2番目の並びの最初の要素が最初の順序付けられた並びに挿入される場所を見つけます。次に、同じアルゴリズムを実行して、最初の並びの最後の要素が2番目の順序付けられた並びに挿入される場所を見つけ、順序付けを維持します。これらの場所の前後の要素はすでに正しい場所にあり、マージする必要はありません。次に、2つの並びの残りの要素のうち小さい方が一時メモリにコピーされ、要素は大きい方の並びとマージされて、現在は空き領域になります。最初の並びが小さい場合、マージは最初から始まります。 2番目が小さい場合、マージは最後から始まります。この最適化により、必要な要素の移動数、実行時間、および一般的な場合の一時的なスペースのオーバーヘッドが削減されます。

例：2つの並び[1、2、3、6、10]と[4、5、7、9、12、14、17]をマージする必要があります。両方の並びはすでに個別にソートされていることに注意してください。 2番目の並びの最小要素は4であり、その順序を維持するために、最初の並びの4番目の位置に追加する必要があります（並びの最初の位置が1であると想定）。最初の並びの最大要素は10であり、順序を維持するために2番目の並びの5番目の位置に追加する必要があります。したがって、[1、2、3]と[12、14、17]はすでに最終位置にあり、要素の移動が必要な並びは[6、10]と[4、5、7、9]です。この知識があれば、5ではなくサイズ2の一時バッファを割り当てるだけで済みます。

マージの方向[編集]

マージは、従来のマージソートのように左から右、または右から左の両方向で実行できます。

マージ中のギャロッピングモード[編集]

要素（青い矢印で示されている）が比較され、小さい方の要素が最終的な位置（赤い矢印で示されている）に移動されます。

配列R1とR2を個別にマージすると、配列から選択された連続する要素の数が保持されます。この数が最小ギャロッピングしきい値（ min_gallop ）に達すると、ティムソートは、その配列から多くの連続する要素がまだ選択されている可能性があると見なし、ギャロッピングモードに切り替えます。 R1がそれをトリガーする責任があると仮定しましょう。このモードでは、アルゴリズムは、配列R1の配列R2の次の要素xに対して、ギャロッピング検索とも呼ばれる指数検索を実行します。これは2つの段階で行われます。最初の段階では、xがである範囲（2 k − 1、2 k + 1 − 1）を見つけます。第2段階では、第1段階で見つかった範囲内の要素xの二分探索を実行します。ギャロッピングモードは、配列中の要素間の間隔のパターンにマージアルゴリズムを適応させる試みです。

すべての赤い要素は青よりも小さいです（ここでは21）。したがって、それらはチャンクで最終配列に移動できます。

ギャロッピングは必ずしも効率的ではありません。場合によっては、ギャロッピングモードでは、単純な線形探索よりも多くの比較が必要になります。開発者が行ったベンチマークによると、ギャロッピングは、一方の配列の最初の要素がもう一方の配列の最初の7つの要素の1つではない場合にのみ有益です。これは、初期しきい値が7であることを意味します。ギャロッピングモードの欠点を回避するために、次の2つのアクションが実行されます。（1）ギャロッピングの効率がバイナリ検索よりも低いことが判明した場合、ギャロッピングモードは終了します。 （2）ギャロッピングの成功または失敗は、 min_gallopを調整するために使用されます。選択した要素が以前に要素を返したのと同じ配列からのものである場合、 min_gallopは1つ減り、ギャロッピングモードへの復帰を促します。それ以外の場合、値は1ずつ増加するため、ギャロッピングモードに戻ることはできません。ランダムデータの場合、 min_gallopの値が非常に大きくなるため、ギャロッピングモードが繰り返されることはありません。 [13]

降順の配列[編集]

降順でソートされたデータも利用するために、ティムソートは、並びを見つけたときに厳密に降順の並びを逆にして、並びのスタックに追加します。降順の実行は後で盲目的に逆になるため、等しい要素を持つ実行を除外すると、アルゴリズムの安定性が維持されます。つまり、等しい要素は逆になりません。

最小配列サイズ[編集]

ティムソートアルゴリズムは、最小サイズの順序付けられたシーケンスminrunsを検索して、そのソートを実行します。

マージは、配列数が2の累乗に等しいか、それよりわずかに少ない場合に最も効率的であり、配列数が2の累乗よりわずかに多い場合は特に効率が低いため、ティムソートはminrunを設定して事前状態を確認します。

Minrunは、データのサイズをminrunで割った値が、2の累乗に等しいか、わずかに小さくなるように、32から64までの範囲から選択されます。最後のアルゴリズムは、配列のサイズの最上位6ビットを取得し、残りのビットのいずれかが設定されている場合は1を追加し、その結果をminrunとして使用します。このアルゴリズムは、64未満の配列を含むすべての配列で機能します。サイズ63以下の配列のために、このセットは、アレイ・サイズに等しいminrunとティムソートは挿入ソートに減少させます。

分析[編集]

最悪の場合、ティムソートでは n要素の配列をソートするために 回の比較が必要になります。入力がすでにソートされているときに発生する最良のケースでは、線形時間で実行されます。これは、ティムソートが適応型ソートアルゴリズムであることを意味します。[3]

オブジェクト参照またはポインタのソートには、クイックソートよりも有利です。これらは、データにアクセスして比較を実行するために高価なメモリ間接参照を必要とし、クイックソートのキャッシュコヒーレンスの利点が大幅に減少するためです。

フォーマル検証[編集]

2015年、EU FP7 ENVISAGEプロジェクトのオランダとドイツの研究者は、ティムソートの標準実装にバグを発見しました。 [14]

具体的には、スタックされた配列サイズの不変量により、必要なスタックの最大サイズの上限が厳しくなります。実装は、2 64バイトの入力をソートするのに十分なスタックを事前に割り当て、それ以上のオーバーフローチェックを回避しました。

ただし、保証では、不変条件を3回の連続配列のすべてのグループに適用する必要がありますが、実装では上位3つのみをチェックしました。 [14]研究者は、Javaソフトウェアのフォーマル検証にKeYツールを使用して、このチェックでは不十分であり、スタックのより深いところで不変条件に違反する結果となるランレングス（およびそれらのランレングスを生成した入力）を見つけることができました。スタックの最上位がマージされた後。 [15]

結果として、特定の入力では、割り当てられたサイズは、マージされていないすべての配列を保持するのに十分ではありません。 Javaでは、これにより、これらの入力に対して配列外の例外が生成されます。 JavaおよびAndroidv7でこの例外をトリガーする最小の入力は、サイズ67108864 （2 26 ）です。 65536 （2 16 ）の特定の入力に対してこの例外が既にトリガーされています）

Javaの実装は、更新された最悪の場合の分析に基づいて、事前に割り当てられたスタックのサイズを増やすことによって修正されました。この記事では、スタック内の最上位の4つの配列が上記の2つのルールを満たしていることを確認することにより、目的の不変条件を確立する方法も形式手法で示しました。このアプローチは、Python [16]とAndroidで採用されました。

参考文献[編集]

  1. ^ Peters, Tim. “[Python-Dev Sorting]”. Python Developers Mailinglist. 2011年2月24日閲覧。 “[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).”
  2. ^ “[DROPS]”. 2018年9月1日閲覧。 “TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.”
  3. ^ a b Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
  4. ^ “[#JDK-6804124 (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort]”. JDK Bug System. 2014年6月11日閲覧。
  5. ^ “Class: java.util.TimSort<T>”. Android Gingerbread Documentation. 2015年7月16日時点のオリジナルよりアーカイブ。2011年2月24日閲覧。
  6. ^ “liboctave/util/oct-sort.cc”. Mercurial repository of Octave source code. 2013年2月18日閲覧。 “Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.”
  7. ^ “Getting things sorted in V8 · V8”. v8.dev. 2018年12月21日閲覧。
  8. ^ “Is sort() stable in Swift 5?” (英語). Swift Forums (2019年7月4日). 2019年7月4日閲覧。
  9. ^ “slice - Rust”. doc.rust-lang.org. 2020年9月17日閲覧。
  10. ^ McIlroy, Peter (January 1993). “Optimistic Sorting and Information Theoretic Complexity”. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 467–474. ISBN 0-89871-313-7 
  11. ^ “listsort.txt”. Python source code (2017年2月10日). 2017年5月6日閲覧。
  12. ^ MacIver (2010年1月11日). “Understanding timsort, Part 1: Adaptive Mergesort”. 2015年12月5日閲覧。
  13. ^ Peters. “listsort.txt”. CPython git repository. 2019年12月5日閲覧。
  14. ^ a b de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (July 2015). “OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case”. Computer Aided Verification: 273–289. doi:10.1007/978-3-319-21690-4_16. http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf. 
  15. ^ de Gouw (2015年2月24日). “Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)”. 2017年5月6日閲覧。
  16. ^ Python Issue Tracker – Issue 23515: Bad logic in timsort's merge_collapse

 

参考文献[編集]

外部リンク[編集]

  • timsort.txt – TimPetersによるオリジナルの説明
「https://ja.wikipedia.org/w/index.php?title=ティムソート&oldid=99440691」から取得