Pythonによるアルゴリズムクイックリファレンス:挿入ソート
アルゴリズムを考えるのは面白い。面白いが基礎も忘れるべからずという事で「アルゴリズムクイックリファレンス」をPythonでコーディングしようかと思う。
挿入ソート
第四章は小手調べ。ここで行うソートはリスト型とかのAPIに組み込んであることがほとんどで、明示的に書くことはまず無い。だが、あえてやってみるというのがいい。ベンチマークをとってみると標準より早い場合もあるので、使ってみる価値はあるかと。
この挿入ソートは配列を順番に見ていって値を比較し、値が大きいものは横にずれていってもらうという方式。アルゴリズムというより力技に近い。
実行時間はこんな感じ
## benchmarker: release 4.0.1 (for python) ## python version: 2.7.6 ## python compiler: GCC 4.8.2 ## python platform: Linux-3.13.0-48-generic-i686-with-Ubuntu-14.04-trusty ## python executable: /usr/bin/python ## cpu model: Intel(R) Core(TM) i5-4310U CPU @ 2.00GHz # 2501.058 MHz ## parameters: loop=1000, cycle=1, extra=0 ## real (total = user + sys) default 0.0594 0.0600 0.0600 0.0000 insertion 0.3498 0.3500 0.3500 0.0000 ## Ranking real default 0.0594 (100.0) ******************** insertion 0.3498 ( 17.0) *** ## Matrix real [01] [02] [01] default 0.0594 100.0 588.8 [02] insertion 0.3498 17.0 100.0
defaultというのはlist#sort()を実行した結果で、今回の挿入ソートがinsertion。比較すると実行速度はdefaultにかなわない事がわかった。ベンチマークにはBenchmarkerを使った。
という事で、しばらくやってみよう
- 作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 11人 クリック: 656回
- この商品を含むブログ (68件) を見る