あいつの日誌β

人生はお酒があれば何とかなります。 drunkard.tokyo

フィボナッチ数列で学ぶ Dynamic Programming

あらすじ

最近求職活動をしているのですが、ホワイトボードにフィボナッチ数列を書いて下さいって言われた時に備えておこうと思いました。しばらく書いてないとどうやって書いていいかわからなくなるので焦る。

そういうわけでフィボナッチ関数の記事を書いていたらいつのまにか Dynamic Programming の記事っぽくなった。

要約

フィボナッチ関数を以下の3段階でグレードアップしていきます。こういう手順踏むと Dynamic Programming ぽいです。という雰囲気をお伝えしたいと思います。

フィボナッチ数列について

イタリアの数学者フィボナッチにちなんで名付けられた数列です。 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 みたいななんかそんなの。

A: とりあえず素直に再帰処理で書いてみる

オーソドックスな書き方は以下の通り。だいたいの面接はここまでで十分です。面接官はホワイトボードにコードを書き出せるかどうかしか見ない気がします。

// const _ = require('lodash');
let count = 0;
function fib(n) {
  count++;
  if (n === 1 || n === 2) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

// const numbers = _.times(10, i => fib(i+1));
console.log(fib(20), count);

結果は以下の通り

6765 13529

さて、これだとO(2**n) なので n の数が増えると大変な事になります。 というわけで memoise*1 します。

B: メモアイズしつつ再帰処理

memoize しましょう

const _ = require('lodash');
let count = 0;

function fib(n, memo) {
  count++;
  if (memo[n]) {
    return memo[n]
  }

  let result;
  if (n === 1 || n === 2) {
    result = 1;
  } else {
    result = fib(n-1, memo) + fib(n-2, memo);
  }
  memo[n] = result;
  return result;
}

console.log(fib(20, []), count);

実行結果

6765 37

関数を呼び出す関数が劇的に減りました。これでどんな n が来ても勝てる!

とはなりません。

再帰処理は n の数を const result = fib(10000, []); みたいに増やすと以下のようなエラーが出ます。さてどうしよう。

function fib(n, memo) {
            ^

RangeError: Maximum call stack size exceeded

C: ボトムアップして再帰処理を無くす

というわけでさっきまでは関数呼んで、呼ばれた関数がメモアイズしている値を返していたのですが時々重複した fib(n) を呼び出しています。これを解消してみます。

const _ = require('lodash');

function fib(n) {
  const memo = []; 
  if (n === 1 || n === 2) {
    return 1;
  }
  memo[1] = 1;
  memo[2] = 1;

  for (let i = 3; i <= n; i++) {
    memo[i] = memo[i-1] + memo[i-2];
  }
  return memo[n];
}

console.log(fib(20), count);

実行結果。 n = 10000 にしても RangeError でなくなりました。やったね。

6765 1

まとめ

というわけで以下のようにアルゴリズムを改良したことによって処理が高速になりました。

A: 再帰処理による関数の呼び出し回数が尋常ではない B: Memoize によって関数を呼び出す回数が激減 C: トップダウンからボトムアップの処理に変更

というわけでフィボナッチ関数の記事書いてたらいつの間にか Dynamic Programming の記事っぽくなりましたとさ。おしまい。

*1:momorise ではない