0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

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

Last updated at Posted at 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 + "回です。")

参考

0
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?