ティムソート単語

ティムソート
1.7千文字の記事
  • 3
  • 0pt
掲示板へ

ティムソートはソートアルゴリズムの一種。ティムさん(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
記事編集 編集履歴を閲覧

ニコニ広告で宣伝された記事

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

ティムソート

1 ななしのよっしん
2020/03/06(金) 11:10:29 ID: usIKNpZwkM
Pythonドキュメントに書いてあったワードで調べたらめっちゃ実用的な大百科が出てきた
助かります
👍
高評価
0
👎
低評価
0
2 ななしのよっしん
2022/06/06(月) 06:31:41 ID: +JSaYFnTG9
他のウェブサイトよりもわかりやすい技術系, 科学系の記事助かる
👍
高評価
0
👎
低評価
0