フィボナッチ数列は黄金分割数列とも呼ばれ、数学者レオナルド・フィボナッチがウサギの繁殖の例として紹介したことから、「ウサギ数列」とも呼ばれています。
// フィボナッチ・ケース
// バニーカウンティング
// 月： 1 2 3 4 5 6 7 8 9 10 11
// 数： 1 1 2 3 5 8 13 21 34 55 89
ブロンズ
function fib(n){
if(n === 1 || n === 2) return 1
return fib(n - 1) + fib(n - 2)
}
シルバー
パフォーマンスについてはどうだろう？
let count = 0 // カウント： fib関数が何回再帰したかをカウントする。
function fib(n){
count++
if(n === 1 || n === 2) return 1
return fib(n - 1) + fib(n - 2)
}
console.log(fib(40)); // 102334155
console.log(count); // 204668309
40ヶ月の時点でCOUNTは204668309回走ったことになります。
// キャッシュ：データを格納するコンテナ。
// jsでキャッシュを実装する方法：キャッシュ・コンテナとして配列またはオブジェクトを使用し、値を格納するためにキーを使用し、キーから値をフェッチする。，
// 値の保存と取り出しが可能である。
// キャッシュを使うアイデア
// 1. 最初に結果を計算するのではなく、対応するデータがキャッシュにあるかどうかを判断する。
// 2. 利用可能であれば、キャッシュ内の対応するデータを直接取得する。
// 3. そうでない場合は、先に進んで結果を計算し、次回のためにキャッシュに保存する。
// このケースでのキャッシュの使い方
let cache = {
// 月をキー、月数を値とする。
// 1: 1,
// 2: 1,
// 3: 2,
// 4: 3
};
// 再帰を使って10ヶ月目のウサギの数を計算する。
let count = 0 // カウント： fib関数が何回再帰したかをカウントする。
function fib(n){
count++
// nヶ月目のウサギの数を求める
// 2.
if(n === 1 || n === 2) return 1
if (cache[n]) {
// 説明：その月の数量の値はキャッシュにあり、データは直接キャッシュから取り出される。
return cache[n]
} else {
// 月数がキャッシュにないことを示す
let ret = fib(n - 1) + fib(n - 2) // 計算結果
// 結果をキャッシュに保存する
cache[n] = ret
// 結果を返す
return ret
}
}
console.log(fib(40));
console.log(count);
// 月 最適化前の回数 最適化後の回数
// n = 10カウント= 109 17
// n = 11カウント= 177 19
// n = 12カウント= 287 21
// n = 20カウント= 13529
// n = 21カウント= 21891
// n = 40カウント= 204668309 77
ゴールド
グローバルに公開されるキャッシュについて考えてみましょう。
// クロージャを使ってキャッシュ・データを保護する
function outer(){
// このケースでのキャッシュの使い方
// キャッシュ内のデータは計算の結果であり、完全に信頼されるべきである。
// キャッシュ内のデータは絶対に正しく、変更できないものでなければならない。
let cache = {
// 月をキー、月数を値とする。
// 1: 1,
// 2: 1,
// 3: 2,
// 4: 3
};
// 再帰を使って10ヶ月目のウサギの数を計算する。
function fib(n){
// nヶ月目のウサギの数を求める
// 2.
if(n === 1 || n === 2) return 1
if (cache[n]) {
// 説明：その月の数量の値はキャッシュにあり、データは直接キャッシュから取り出される。
return cache[n]
}
return cache[n] = fib(n - 1) + fib(n - 2)
}
return fib
}
let ret = outer()
console.log(ret(40))
要約すると
フィボナッチの場合はテクニカルポイントを使用します：
- 再帰：計算結果
- キャッシュ：計算されたデータを保存
- クロージャ：キャッシュデータの保護
