ティムソートはソートアルゴリズムの一種。ティムさん(Tim Peters)が作ったからティムソート。
「ソートは研究室で動いてるんじゃない、現場で動いてるんだ」がモットーの実利派設計。オーダー的にも平均O(n log n)というデキるソートの条件を満たしながら、最悪O(n log n)と最良O(n)がくっついてしかも安定ソートというオットコマエな子。
実装がお目見えしたのは2002年のPython上という、これぞモダンアルゴリズムと言った感のあるソートである。まあ中身は大体マージソートだが。
実利的ものさし
原理の前に、そもそもソートの性能はどうやって測るのかという話をしよう。
普通ソートアルゴリズムの計算回数はデータの内容によって変動が発生する。例えば高速で知られるクイックソートもうっかりO(n^2)を出すことがあるという爆弾持ちであるし、普段は大した事ないがソート済みに近いと強い挿入ソートとか色々癖がある。そこで一般的なパターンとしては、ソート済み、逆順、ランダム、ぐらいのケースを測ることになる。このうち平均性能評価の基本となるのはもちろんランダムな配列である。
で、ティムソートのそもそもの着想は「ちょい待ち、そのサンプルは非現実的なベンチマークなんじゃねえの?」と考えた点である。何故か。
実用的なプログラムでデータをソートする時、ソート済みや逆順はともかく、完全にランダムな配列が入ってくることは少ない。大抵のケースでは部分的にランダムだったり整っていたりするものなのだが、そういった現実味のあるデータに対する最適化は意外と考慮されてこなかった。元々ある程度揃った部分があるなら、それをすてるなんてとんでもない!と考えるべきなんじゃない?
例えばこんなデータである。
5 | 39 | 4 | 8 | 12 | 55 | 2 | 9 |
なるほど、確かにこの配列はソート済みと言えない。しかし5,39と4,8,12,55と2,9の部分はそこだけ見ると順番に並んでいるから、できればこれを手付かずに済ませたいわけだ。問題はそれぞれをどう組み合わせるかであって、すべての値を対等に捉える必要はない。
以上前置き。
原理
大枠としてはナチュラルマージソートと呼ばれるマージソートの一種を使う。オリジナルのマージソートは配列を適当に等分してマージするアルゴリズムだが、ナチュラルマージソートは配列の中で元々並んでいる部分を一単位としてマージしていく方式である。
しかしマージソートは処理が大掛かりなため小さな配列に対してはオーバーヘッドが大きい。そこで、ある程度大きな塊になるまでトリビアルなアルゴリズムで並び替えた方が有利である。ティムソートの場合最大64個までは挿入ソートで塊を作るとしており、ある程度ダマができたところでマージソートに切り替える。
マージソートの方式についても色々と工夫があるのだが、まあ細かいことはアルゴリズムの教科書でも読んだ方がいいだろう。使用メモリ量であるとかキャッシュとの相性とか色々配慮されており、現代的な工夫を垣間見ることができる。
性能評価
ソート済み配列に対してはソート不要でO(n)をだし、またソート済みに近いほど速いという特性のため、条件によってはクイックソートと互角以上に戦えるアルゴリズムである(というか、ここまでやってまだ互角なのかよ!という話だが)
ただ、どちらかと言うと最悪でもO(n log n)かつ安定ソートという所に強みがあって、ポジション的には(アルゴリズム的にも)マージソートの改良版みたいな感じである。
処理が複雑化した分、完全にランダムなデータを相手にするとノーマルのマージソートより少し悪くなるという難点もあるが、最初に書いたとおり、「ランダムなデータなんて無菌室にしかねーよ」という発想に基づくので、実アプリ開発をする上ではまず間違いなく良くなっていると思っていい。また元々複合アルゴリズムなので、小さな配列を渡した時自動的に挿入ソートに切り替わるという使い勝手の良さもある。
ちなみにJava8やAndroidのデフォルトソートアルゴリズムはティムソートである。これはやはり総合的な安定性を評価されてのことだろう。まあ実装がバグ騒ぎ起こしたりもしてるけど。
関連項目
- 3
- 0pt