高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解

[mohno]

「後にベンチマークの誤りと判明」←なんだぁ。

[tanakh]

せるクマー

[y-kawaz]

つまり複数のアルゴリズムな得意なパターンを上手く繋ぎあわせて全体として高速安定を保つようにしたアルゴリズムキメラがTimSortってことか。なんか #gdd11jp のスライドパズルで色々試したのを思い出したわ。

[sifue]

新しい方法がまだ出てくるって本当にすごいことだと思う

[gfx]

たしかにオリジナルのコードは複雑で、移植したのにぜんぜん何やってるかわかりませんでした

[shiba_yu36]

普通に難しい...

[chanpon0]

ソートアルゴリズム4つ

[Kshi_Kshi]

TimSort

[kireifish]

Java SE 7、およびAndroidでの標準ソートアルゴリズム

[tmatsuu]

ほう

[anoncom]

SleepSortの話しと勘違いしてた。

[an-ironic-man]

8割くらいわかってないけど、ソートのアルゴリズムの話はいつもおもしろいと感じる。

[naga_sawa]

ヒープソートをベースに、アダプティブにソート方法を切り替えて安定・高速化したソート

[labunix]

高速な安定ソートアルゴリズム “TimSort” の解説

[zakinco]

へー

[takfjt]

これは面白い。そして、このアプローチはまだ攻める余地がありそうだ。

[richard_raw]

sleep sortだと思ってましたてへ。アルゴリズム勉強しないとなあ……。

[fabled]

他の主要ソートの知識前提での解説

[rti7743]

めも

[luccafort]

未だにこういう根幹のシステムと言うかアルゴリズムが改善していくってすごい根気だと思う。 [あとで読む]

[atyks]

高速な安定ソートアルゴリズム “TimSort” の解説 : Preferred Research

[radiocat]

実行する側の人間だと改めて認識…

[negima1976]

おもしろいな

[yamakaz]

ふむふむわからん

[syanbi]

TimSort

[sh2]

マージソートの前段をショートカットしているのか

[yoshihiko_k]

あとで見る

[nabetama]

必要に迫られる時がこないと覚えないだろうけど、とりあえず読んでおく。

[dekatotoro]

高速な安定ソートアルゴリズム “TimSort” の解説

[economixmeister]

初めて聞く"TimSort"アルゴリズムの解説。

[lettas0726]

明日の朝読む

[uzuki-first]

memo

[inulab]

やっぱりよく考えるなぁと思う

[AndroidestX]

高速な安定ソートアルゴリズム “TimSort” の解説 : Preferred Research