JavaScriptでフィボナッチ数を求めて実行速度を計測

Contents

1 はじめに
2 オーソドックスな再帰で書く
3 ループを使って書く
4 配列を使って書く
5 足し上げていく方法
6 メモ化を使って書く
7 末尾再帰を使って書く
8 おわりに

はじめに

こんにちは、野村です。

今回は、いくつかの方法でフィボナッチ数を求めるスクリプトを書き、それぞれの実行速度を計測してみます。
スクリプトはJavaScriptを使います。

オーソドックスな再帰で書く

とても遅いです。
なので、この方法だけは33番目のフィボナッチ数を求めます。

'use strict';

const fib00 = (n)=>{
  return (n<2) ? n : fib00(n-2) + fib00(n-1);
}
console.time('timer00');
console.log(fib00(33));
console.timeEnd('timer00');

実行結果

3524578
timer00: 46.427ms

ループを使って書く

以下のものからは1000番目のフィボナッチ数を求めます。

'use strict';

const fib01 = (n)=>{
  let a = 0;
  let b = 1;
  let c;
  for(let i=0; i<n; i++){
    c = a;
    a = b;
    b = a+c;
  }
  return a;
}
console.time('timer01');
console.log(fib01(1000));
console.timeEnd('timer01');

実行結果

4.346655768693743e+208
timer01: 0.688ms

配列を使って書く

'use strict';

const fib02 = (n)=>{
  let a = Array(0,1);
  for(let i=2; i<=n; i++){
    a[i] = a[i-2] + a[i-1];
  }
  return a[n];
}
console.time('timer02');
console.log(fib02(1000));
console.timeEnd('timer02');

実行結果

4.346655768693743e+208
timer02: 0.772ms

足し上げていく方法

末尾再帰と似ているけど、方向が逆。
うまい表現ができないので「足し上げる」という言葉を勝手に作ってみた。

'use strict';

const fib03 = (n,a,b,i)=>{
  return (n===i) ? a : fib03(n,b,a+b,i+1);
}
console.time('timer03');
console.log(fib03(1000,0,1,0));
console.timeEnd('timer03');

実行結果

4.346655768693743e+208
timer03: 1.894ms

末尾再帰と同程度と考えていたけど、結構遅かった。

メモ化を使って書く

いまいち理解できた気がしないけど、メモ化ってこんな感じだと思う。

'use strict';

const fib04 = (n)=>{
  let memo = Array();
  const loop = (m)=>{
    if (m<2) return m;
    if (memo[m] !== undefined) return memo[m];
    return memo[m] = loop(m-2) + loop(m-1);
  }
  return loop(n);
}
console.time('timer04');
console.log(fib04(1000));
console.timeEnd('timer04');

実行結果

4.346655768693743e+208
timer04: 0.395ms

末尾再帰を使って書く

'use strict';

const fib05 = (n,a,b)=>{
  if (n==0) return 0;
  if (n==1) return b;
  return fib05(n-1,b,a+b);
}
console.time('timer05');
console.log(fib05(1000,0,1));
console.timeEnd('timer05');

実行結果