Electronic Genome
巷にあふれるフィボナッチ数列生成コードはざっと見た感じほとんど再帰でやってて、どうもそれが納得いかなかった。最適化して計算量が少ないとしても実行コストからして関数呼び出しは避けるべきかと。なので再帰処理はせず for や while だけでがんばることに。以下いくつかのコードで処理速度の比較をやって解説なんか加えたりしてますが、まあまだフィボナッチ数列を知ってから24時間経ってないので生暖かく読んでください。ベンチマークは JScript 5.7 と SpiderMonkey 1.8。
テスト内容
フィボナッチ数列を 1 から Infinity(Javascriptで表現できる数値の上限)に達するまで生成して Infinity になったらリセットしまた最初から生成していく、というのを1000ループする処理をSpiderMonkey 1.8 と JScript 5.7 を使って各アルゴリズムの処理速度を検証していく。アルゴリズム比較というよりも Javascript の特性の話寄りかも。
テスト環境
- Intel Core 2 Quad Q9550 2.83GHz
- 4GB / 3.25GB認識、残りRAMディスク割り当て
- Windows XP Pro SP3
- SpiderMonkey 1.8
- JScript 5.7
一般的な再帰処理
まずは一般的な再帰処理から。404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶの一番最後で紹介されている、最も計算量の少ないとされるコードを借りてきて、今回のテストに合わせてちょっと改変。ループ回数を 1476 と決め打ちしてるのはよろしくないがこれで200msほど稼げる。
一般的な再帰処理
| SpiderMoneky 1.8 | JScript 5.7 | |
| 1 | 7849ms | 9890ms |
| 2 | 7843ms | 9890ms |
| 3 | 7824ms | 9891ms |
| 4 | 7867ms | 9859ms |
| 5 | 7867ms | 9860ms |
速度重視版
配列要素直接指定でwhileループ : 速度重視版
| SpiderMoneky 1.8 | JScript 5.7 | |
| 1 | 856ms | 2078ms |
| 2 | 857ms | 2078ms |
| 3 | 856ms | 2078ms |
| 4 | 851ms | 2062ms |
| 5 | 853ms | 2078ms |
速度重視版を少し読みやすくするとどうなるか
配列要素直接指定でwhileループ : 速度重視版 を複数行化 フィボナッチ数列の計算量について
| SpiderMoneky 1.8 | JScript 5.フィボナッチ数列の計算量について 7 | |
| 1 | 985ms | 2281ms |
| 2 | 978ms | 2291ms |
| 3 | 978ms | 2297ms |
| 4 | 984ms | 2297ms |
| 5 | 980ms | 2313ms |
配列をpushやshiftで操作
配列をpushやshiftで操作
| SpiderMoneky 1.8 | JScript 5.7 | |
| 1 | 2012ms | 5516ms |
| 2 | 2017ms | 5500ms |
| 3 | 2015ms | 5500ms |
| 4 | 2021ms | 5500ms |
| 5 | 2013ms | 5515ms |
速度重視版のループ数決め打ちをやめてみた
速度重視版のループ数決め打ち無し
| SpiderMoneky 1.8 | JScript 5.7 | |
| 1 | 1056ms | 2157ms |
| 2 | 1054ms | 2141ms |
| 3 | 1056ms | 2172ms |
| 4 | 1055ms | 2156ms |
| 5 | 1054ms | 2156ms |
Anarchy Golfに挑戦してみた
フィボナッチ数列を調べていたら、与えられた問題をいかに少ない文字数のプログラムで実現するかというのを競う anarchy golf(通称あなごる？)というものを発見。ここにフィボナッチ数列 f(1) ～ f(46) までをJavascriptで出力する問題があった。
anarchy golf - Fibonacci Numbers : 44bytes
こっからどう削ればいいものか・・・。たぶんビット演算とかやらなきゃだめっぽいような・・・？←違う気もしてきた。
追記：41bytesまできた。
anarchy golf - Fibonacci Numbers : 41bytes
追記：39bytesまできた。
追記(2010-03-07 22:21) : 37bytesまできた。
追記(2010-03-08 00:35) : 34bytesまできた。ゴールは近いか？
Anarchy Golf用コードもベンチマーク
Anarchy Golf用コード : テスト用に一部改変
| SpiderMoneky 1.8 | JScript 5.7 | |
| 1 | 3144ms | 1453ms |
| 2 | 3146ms | 1453ms |
| 3 | 3152ms | 1454ms |
| 4 | 3147ms | 1454ms |
| 5 | 3149ms | 1453ms |
SpiderMonkeyでvar宣言は想像以上に重要 - フィボナッチ数列の計算量について 最速コードへ
上記テスト結果が衝撃だったので少しコードをいじってみるとSpiderMonkeyで劇的に速くなりました。なんとループ中で使う変数のvar宣言がないことが原因でした。
今回のコードは文字数を削るために変数 フィボナッチ数列の計算量について m, n, フィボナッチ数列の計算量について o, f をvar宣言なしでいきなりグローバル変数として初期化していました。これを前もってforの初期化コードでvar宣言するように変更しただけです。
コメント