スポンサーサイト
投稿日時 : -------- --:--
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
-------- --:-- | スポンサー広告
フィボナッチ数列でJavascriptアルゴリズム速度比較とAnarchy Golf
投稿日時 : 2010-03-02 05:56
更新日時 : 2010-03-08 00:35
 プログラマーの力量を見極める--面接官になったら尋ねるべき質問実例集 - IT業界を生き抜く秘密10箇条 - ZDNet Japan
 
↑の記事を読んでて文系出なのを言い訳にして今までフィボナッチ数列が何なのかよく知らないまま来てしまったことに危機感を覚えたのでやってみた。基本的な話はグーグル先生にまかせておくとして、実際のコードを紹介。
 
 巷にあふれるフィボナッチ数列生成コードはざっと見た感じほとんど再帰でやってて、どうもそれが納得いかなかった。最適化して計算量が少ないとしても実行コストからして関数呼び出しは避けるべきかと。なので再帰処理はせず 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
 
以下のコードで処理中の print がコメントアウトされているのは SpiderMonkey の標準出力がボトルネックすぎてフィボナッチ数列の生成速度自体がわからなくなるので。コメント外せば普通に数列が表示されます。
 

一般的な再帰処理

 まずは一般的な再帰処理から。404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶの一番最後で紹介されている、最も計算量の少ないとされるコードを借りてきて、今回のテストに合わせてちょっと改変。ループ回数を 1476 と決め打ちしてるのはよろしくないがこれで200msほど稼げる。
   
一般的な再帰処理
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
function fib(n){
  if (fibs[n]) return fibs[n];
  if (n <= 2) return 1;
  return fibs[n] = fib(n-1) + fib(n-2);
}
var fibs;
var n;
for(var i=0; i<1000; i++){ //1000回ループ
	fibs = {};
	for (n = 1; n <= 1476; n++) fib(n); //print(fib(n));
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
17849ms9890ms
27843ms9890ms
37824ms9891ms
47867ms9859ms
57867ms9860ms
遅い!遅すぎる。すごい待たされる感があります。
 

速度重視版

 次に最速に近いスコアをマークしたやつを(最速のコードは驚きと共に最後に登場)。
 
配列要素直接指定でwhileループ : 速度重視版
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0, f, j, a; i<1000; i++){ //1000回ループ
	f = 1, j = 0, a = [0, 1];
	while(j < 1476){ //1476ループ目でfがInfinityに達する
		//print(f);
		a[j + 2] = (f += a[j++]);
	}
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
1856ms2078ms
2857ms2078ms
3856ms2078ms
4851ms2062ms
5853ms2078ms
 一般的な再帰処理に比べて1/10近いスコア。a への代入を push などを使うのではなく a[j + 2] のように要素を直接指定している。
 

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

 速度重視版のコードは一般的には複数行に分けて書くようなものを1行にまとめている。以下のようなコードは読みにくい上に処理される順序がわかりにくいので悪いコードだとされている。
a[j + 2] = (f += a[j++]);
これを少し読みやすく複数行に分けて書いて速度を測ってみる。
 
配列要素直接指定でwhileループ : 速度重視版 を複数行化
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0, f, j, a; i<1000; i++){
	f = 1, j = 0, a = [0, 1];
	while(j < 1476){ //1476ループ目でfがInfinityに達する
		//print(f);
		f += a[j];
		j++;
		a[j+1] = f;
	}
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
1985ms2281ms
2978ms2291ms
3978ms2297ms
4984ms2297ms
5980ms2313ms
なんとSpiderMonkeyで100msちょっと、JScriptで200ms遅くなってしまった。速度が求められる処理では多少読みにくくても1行にまとめた方が良さそうなことがわかる。処理される順番などについて念入りにたくさんコメントをつけておけばバグを生む可能性もまあ少なくなると思う。
 

配列をpushやshiftで操作

 速度重視版の配列をpushやshiftで操作した場合。ロケット鉛筆的な動作。配列要素は常に2つ。
 
配列をpushやshiftで操作
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0, n, f, a; i<1000; i++){
	for(n=0, f=1, a=[0,1]; n<1476; n++){ //1476ループ目でfがInfinityに達する
		//print(f);
		a.push(f += a.shift());
	}
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
12012ms5516ms
22017ms5500ms
32015ms5500ms
42021ms5500ms
52013ms5515ms
それなりに時間はかかるがまあ許せる範囲。速度重視版との違いは配列操作にpushやshiftを使っている点。pushやshiftは遅い。
 

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

 やっぱり決め打ちはよくないよ、ということでちゃんとしたらどうなるかテスト。
 
速度重視版のループ数決め打ち無し
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0, f, j, a; i<1000; i++){
	f = 1, j = 0, a = [0, 1];
	while(f < Infinity){ //Infinityになったら終了
		//print(f);
		a[j + 2] = (f += a[j++]);
	}
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
11056ms2157ms
21054ms2141ms
31056ms2172ms
41055ms2156ms
51054ms2156ms
というように200msほど遅くなってしまうわけです。
 

Anarchy Golfに挑戦してみた

 フィボナッチ数列を調べていたら、与えられた問題をいかに少ない文字数のプログラムで実現するかというのを競う anarchy golf(通称あなごる?)というものを発見。ここにフィボナッチ数列 f(1) ~ f(46) までをJavascriptで出力する問題があった。
 
 
で、やってみたわけですが他の人がすごい。1位は32bytesです。32bytesでフィボナッチ!すごすぎです。一応投稿したコードを載せておきます。今のとこ44byteです。
 
anarchy golf - Fibonacci Numbers : 44bytes
for(m=n=o=0,f=1;46>n++;print(o=f),f+=m,m=o);
こっからどう削ればいいものか・・・。たぶんビット演算とかやらなきゃだめっぽいような・・・?←違う気もしてきた。
 
追記:41bytesまできた。
anarchy golf - Fibonacci Numbers : 41bytes
for(f=m=1,n=46;n--;[m,f]=[f+m,m])print(f)
追記:39bytesまできた。
 
追記(2010-03-07 22:21) : 37bytesまできた。
 
追記(2010-03-08 00:35) : 34bytesまできた。ゴールは近いか?
 

Anarchy Golf用コードもベンチマーク

 実は大きな発見がありました。
 
Anarchy Golf用コード : テスト用に一部改変
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0; i<1000; i++){
	for(m=n=o=0,f=1;1476>n++;o=f,f+=m,m=o);
	//for(m=n=o=0,f=1;1476>n++;print(o=f),f+=m,m=o); //print付
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
13144ms1453ms
23146ms1453ms
33152ms1454ms
43147ms1454ms
53149ms1453ms
SpiderMonkeyよりJScriptが速い!?何かの間違いかと思ってコード見返したけど問題ない。ここで偶然にもSpiderMonkeyの特性を発見することになった。
 

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

 上記テスト結果が衝撃だったので少しコードをいじってみるとSpiderMonkeyで劇的に速くなりました。なんとループ中で使う変数のvar宣言がないことが原因でした。
 今回のコードは文字数を削るために変数 m, n, o, f をvar宣言なしでいきなりグローバル変数として初期化していました。これを前もってforの初期化コードでvar宣言するように変更しただけです。
 
Anarchy Golf用コード : テスト用に一部改変 - var宣言は重要
//var print = function(x){WScript.Echo(x)} //JScript用
var s = new Date(); //処理開始時刻保存
for(var i=0,m,n,o,f; i<1000; i++){
	for(m=n=o=0,f=1;1476>n++;o=f,f+=m,m=o);
	//for(m=n=o=0,f=1;1476>n++;print(o=f),f+=m,m=o); //print付
}
print(new Date()-s); //処理にかかった時間をミリ秒で表示
SpiderMoneky 1.8JScript 5.7
1694ms1453ms
2694ms1437ms
3697ms1453ms
4695ms1438ms
5696ms1453ms
なんと!var宣言するだけでSpiderMonkeyで最速スコアに。JScriptの方は改良前と誤差の範囲。SpiderMonkeyの場合var宣言はスコープの範囲だけの問題ではなく、速度に大きく影響するようです。この原因や仕組みについてはまだ詳しく調べていませんが、スコープチェーンをたどるかたどらないかの違いかもなーとぼんやり考えています。まあいずれにせよ大きな発見でした。
 
かなり速くなったけどまだまだ上はあると思います。anarchy golfもまだまだです。修行あるのみ。
 
 
スポンサーサイト
2010-03-02 05:56 | Javascript | Comment(0) | Trackback(0)
Comment
コメントを書く
#

管理者にだけ表示
Trackback
Trackbak URL:http://itmst.blog71.fc2.com/tb.php/192-8f09a284
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。