エラー処理を書いてはいけない

preferred

2011-12-09 14:55:55

昨日セミナーとして USTREAM させていただいた資料を公開いたします。

エラー処理を書いてはいけない

USTREAMのビデオ

タイトルは釣り気味ですが、内容はいたって真面目なのでご安心ください。

続きを読む »

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

preferred

2011-10-26 19:36:54

先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。

C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。

しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解説してみたいと思います(クイックソートマージソートヒープソート挿入ソートの知識を前提とします)。

続きを読む »