【Javascript】Dynamic Programming（動的計画法）を使った、フィボナッチ数列の実装

はじめに

Dynamic Programming（動的計画法）について勉強したのでまとめます。

Dynamic Programming（動的計画法）とは？

Dynamic Programming（動的計画法）とは？

・キャッシュを使った最適化の手法 → 一度解いた計算をキャッシュに保存しておき、計算コストを削減する（典型例：フィボナッチ数列）。

・フィボナッチ数列：前の２つの数字を足すと、次の数字になる（再掲）。
例）0, 1, 1, 2, 3, 5, 8, 13,...

※ フィボナッチ数列を単純に計算する場合、O(2^n)となり、恐ろしく計算コストがかかる。。
これをキャッシュを使って解くことで、計算コストをO(n)まで抑えることが可能。
（実装パートに、両パターンのコードを記載）

登場する重要なワード

・キャッシュ：値を保存しておき、後で使えるようにすること。

・グローバルスコープ：プログラムのどこからでも参照できる。そのためクロージャを使用する必要あり。

・クロージャ：メソッドを他のプログラムから変更されないように制御できる。

実装

ここでは、以下の項目についての実装例を示す。
・キャッシュの使い方
・フィボナッチ数列（キャッシュを使用しない場合と、使用した場合について）

キャッシュの使い方

cache.js

// パターン１：キャッシュの例
let cache = {};
function memorizedAddTo70(n) {
  if (n in cache) {
    return cache[n];
  } else {
    console.log("long time");
    cache[n] = n + 70;
    return cache[n];
  }
}

// テスト
console.log("1:", memorizedAddTo70(8));
console.log("2:", memorizedAddTo70(10));
console.log(memorizedAddTo70(16));


// パターン２：基本的にはグローバルスコープを汚さないようにするので、そちらの実装例を以下に示す。（クロージャを使用）
function memorizedAddTo60() {
  let cache = {}
  return function(n) {
    if (n in cache) {
      return cache[n];
    } else {
      cache[n] = n + 60
      return cache[n];
    }
  }
}

// この書き方の場合、console.log(memorizedAddTo60(8));みたいな書き方だと、[Function (anonymous)]になるので、一旦インスタンス化したものを定数に格納してやる。
const memorized = memorizedAddTo60();
console.log("1:", memorized(17));

フィボナッチ数列

・フィボナッチ数列：前の２つの数字を足すと、次の数字になる（再掲）。
例）0, 1, 1, 2, 3, 5, 8, 13,...

fibonacci.js

// フィボナッチ数列の実装（単純に実装した場合） → 計算時間：O(2^n)
// 計算回数を標示させる用
let calculationsNormal = 0

function fibonacci(n) {
  // インデックス番号が-にならないように条件式をつける
  calculationsNormal++;
  if (n < 2) {
    return n
  };
  // 前の２つの数字を足し合わせる
  return fibonacci(n-1) + fibonacci(n-2);
};

// テスト（ノーマルバージョン）
console.log("normal:", fibonacci(45));
console.log("cacheを使わなかった場合:計算回数は" + calculationsNormal + "回です。")


// Dynamic Programmingで実装した場合 → 計算時間：O(n)
// 計算回数を表示させる用
let calculationsMod = 0

function fibonacciMod() {
  // 空のキャッシュを作成
  let cache = {};
  // クロージャーを使用
  return function fib(n) {
    // 参考に計算回数を表示させる。
    calculationsMod++;
    // cacheの中に数字があれば、それを使用する
    if (n in cache) {
      return cache[n];
      // なければ、キャッシュに保存する
    } else {
      // 保存する値を明示
      // インデックス番号nが0, 1の時はn-2が負の数になってしまうため、インデックス番号(n)をそのまま返す。
      if (n < 2) {
        return n;
      // それ以外の時（n >= 2）は、２つ前と１つ前の値を足したものを返す。
      } else {
        cache[n] = fib(n-1) + fib(n-2);
        return cache[n];
      }
    }
  }
};

// テスト（キャッシュを使用したバージョン）
const fasterFib = fibonacciMod();
console.log("Dynamic Programming:", fasterFib(45));
console.log("cacheを使った場合:計算回数は" + calculationsMod + "回です。")

// 再度ノーマルのファンクション（計算スピードが全然違うことが分かるはず！）
console.log("normal:", fibonacci(45));


// おまけ：ボトムアップ・アプローチ
// 計算回数用
let calculationsMod2 = 0;

function fibonacciMod2(n) {
  // 初期のリストを定義
  let answer = [0, 1];
  for (let i = 2; i <= n; i++) {
    calculationsMod2++;
    answer.push(answer[i-2] + answer[i-1]);
  };
  return answer.pop();
};


// テスト
console.log("ボトムアップ・アプローチ:", fibonacciMod2(45));
console.log("ボトムアップ・アプローチを使った場合:計算回数は" + calculationsMod2 + "回です。")

参考