外為トレードバトル

フィボナッチ数列の計算量について

フィボナッチ数列の計算量について
これは再帰関数を用いて計算することができます。 フィボナッチ数列の計算量について i 番目の荷物を選択するかしないかで分岐させてください。

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.8JScript 5.7
17849ms9890ms
27843ms9890ms
37824ms9891ms
47867ms9859ms
57867ms9860ms
遅い!遅すぎる。すごい待たされる感があります。

速度重視版

配列要素直接指定でwhileループ : 速度重視版

フィボナッチ数列の計算量について
SpiderMoneky 1.8JScript 5.フィボナッチ数列の計算量について 7
1856ms2078ms
2857ms2078ms
3856ms2078ms
4851ms2062ms
5853ms2078ms
一般的な再帰処理に比べて1/10近いスコア。a への代入を push などを使うのではなく a[j + 2] のように要素を直接指定している。

速度重視版を少し読みやすくするとどうなるか

配列要素直接指定でwhileループ : 速度重視版 を複数行化

SpiderMoneky 1.8JScript 5.7
1985ms2281ms
2978ms2291ms
3978ms2297ms
4984ms2297ms
5980ms2313ms
なんとSpiderMonkeyで100msちょっと、JScriptで200ms遅くなってしまった。速度が求められる処理では多少読みにくくても1行にまとめた方が良さそうなことがわかる。処理される順番などについて念入りにたくさんコメントをつけておけばバグを生む可能性もまあ少なくなると思う。

配列をpushやshiftで操作

配列をpushやshiftで操作

SpiderMoneky 1.8JScript 5.7
12012ms5516ms
22017ms5500ms
32015ms5500ms
42021ms5500ms
52013ms5515ms
それなりに時間はかかるがまあ許せる範囲。速度重視版との違いは配列操作にpushやshiftを使っている点。pushやshiftは遅い。

速度重視版のループ数決め打ちをやめてみた

速度重視版のループ数決め打ち無し

SpiderMoneky 1.8JScript 5.7
11056ms2157ms
21054ms2141ms
31056ms2172ms
41055ms2156ms
51054ms2156ms
というように200msほど遅くなってしまうわけです。

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.8JScript 5.7
13144ms1453ms
23146ms1453ms
33152ms1454ms
43147ms1454ms
53149ms1453ms
SpiderMonkeyよりJScriptが速い!?何かの間違いかと思ってコード見返したけど問題ない。ここで偶然にもSpiderMonkeyの特性を発見することになった。

SpiderMonkeyでvar宣言は想像以上に重要 - 最速コードへ

上記テスト結果が衝撃だったので少しコードをいじってみるとSpiderMonkeyで劇的に速くなりました。なんとループ中で使う変数のvar宣言がないことが原因でした。
今回のコードは文字数を削るために変数 m, n, o, f をvar宣言なしでいきなりグローバル変数として初期化していました。これを前もってforの初期化コードでvar宣言するように変更しただけです。

関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる