👨‍🎓

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

2023/05/14に公開

はじめに

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

Dynamic Programming(動的計画法)とは?

Dynamic Programming(動的計画法)とは?

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

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

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

登場する重要なワード

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

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

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

実装

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

キャッシュの使い方

cache.js
// パターン1:キャッシュの例
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));


// パターン2:基本的にはグローバルスコープを汚さないようにするので、そちらの実装例を以下に示す。(クロージャを使用)
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));

フィボナッチ数列

・フィボナッチ数列:前の2つの数字を足すと、次の数字になる(再掲)。
例)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
  };
  // 前の2つの数字を足し合わせる
  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)は、2つ前と1つ前の値を足したものを返す。
      } 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 + "回です。")

参考

https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms

Discussion