👨🎓
【Javascript】Dynamic Programming(動的計画法)を使った、フィボナッチ数列の実装
はじめに
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 + "回です。")
参考
Discussion