說(shuō)明
這是在codewars.com上刷的一道js練習(xí)題浓若，在此做個(gè)記錄
問(wèn)題描述
The Fibonacci sequence is traditionally used to explain tree recursion.
斐波那契序列通常是用來(lái)解釋遞歸調(diào)用璃哟。
function fibonacci(n) {
if(n==0 || n == 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
This algorithm serves welll its educative purpose but it's tremendously inefficient, not only because of recursion, but because we invoke the fibonacci function twice, and the right branch of recursion (i.e. fibonacci(n-2)) recalculates all the Fibonacci numbers already calculated by the left branch (i.e. fibonacci(n-1)).
這個(gè)算法以教學(xué)為目的,但非常低效的,不僅因?yàn)檫f歸,而且兩次調(diào)用fibonacci函數(shù),在函數(shù)里面右側(cè)調(diào)用的fibonacci(n-2) 在表達(dá)式左側(cè)調(diào)用fibonacci(n-1)時(shí)就已完全計(jì)算過(guò)一遍。
This algorithm is so inefficient that the time to calculate any Fibonacci number over 50 is simply too much. You may go for a cup of coffee or go take a nap while you wait for the answer. But if you try it here in Code Wars you will most likely get a code timeout before any answers.
這個(gè)算法效率是如此之低,斐波納契數(shù)超過(guò)50的實(shí)在太多了哪工。你可以去喝杯咖啡或去睡午覺(jué)時(shí)等待答案。但如果你就用這個(gè)代碼在codewars上很可能得到一個(gè)超時(shí)錯(cuò)誤。
For this particular Kata we want to implement the memoization solution. This will be cool because it will let us keep using the tree recursion algorithm while still keeping it sufficiently optimized to get an answer very rapidly.
對(duì)于這個(gè)特定卡塔(類似打怪升級(jí)里面的級(jí)數(shù))深寥，我們想實(shí)現(xiàn)緩存的解決方案婉称。這是特別酷的,因?yàn)樗鼘⒆屛覀兝^續(xù)使用遞歸算法,同時(shí)仍然保持足夠迅速的得到一個(gè)答案块仆。
The trick of the memoized version is that we will keep a cache data structure (most likely an associative array) where we will store the Fibonacci numbers as we calculate them. When a Fibonacci number is calculated, we first look it up in the cache, if it's not there, we calculate it and put it in the cache, otherwise we returned the cached number.
memoize的版本的訣竅是,保持一個(gè)緩存數(shù)據(jù)結(jié)構(gòu)(最有可能的關(guān)聯(lián)數(shù)組),將斐波納契數(shù)列的值緩存。當(dāng)獲取一個(gè)斐波那契數(shù)列值時(shí),首先在緩存中查找王暗，如果有則直接返回值,如果沒(méi)有,再計(jì)算并把它放進(jìn)緩存悔据。
Refactor the function into a recursive Fibonacci function that using a memoized data structure avoids the deficiencies of tree recursion Can you make it so the memoization cache is private to this function?
使用memoize的數(shù)據(jù)結(jié)構(gòu)重構(gòu)函數(shù)的遞歸Fibonacci以避免遞歸調(diào)用的缺陷。
分析
斐波那契數(shù)列里面不斷的遞歸調(diào)用自身俗壹，列入輸入的是 70科汗，那么需要計(jì)算69和68的值。
在計(jì)算69的過(guò)程中又計(jì)算了 68绷雏、67头滔、、之众、拙毫、、1棺禾。 計(jì)算 68的過(guò)程又計(jì)算了 67缀蹄、66、膘婶、缺前、、悬襟、衅码、、1的值脊岳，如此重復(fù)計(jì)算的值太多了逝段，花費(fèi)的時(shí)間也就比較多。
緩存思想恰好可以減少不必要的重復(fù)計(jì)算。當(dāng)?shù)谝槐橛?jì)算69的值時(shí)就遞歸計(jì)算了 68、67树灶、66、嘹黔、、1的值莫瞬，之后的每次都先查看是否有緩存儡蔓，有就直接返回緩存值郭蕉，避免了重復(fù)計(jì)算。
代碼
let cache = {};
let fibonacci = function(n) {
if(n==0 || n == 1)
return n;
if(cache[n]){
return cache[n];
}
return cache[n] = fibonacci(n-1) + fibonacci(n-2);
}
性能測(cè)試
//沒(méi)有緩存時(shí)
let tesetNum = 40;
console.time('NoCache');
function fibonacci1(n) {
if(n==0 || n == 1)
return n;
return fibonacci1(n-1) + fibonacci1(n-2);
}
fibonacci1(tesetNum);
console.timeEnd('NoCache');
// 使用緩存時(shí)
console.time("HasCache");
let cache = {};
let fibonacci = function(n) {
if(n==0 || n == 1)
return n;
if(cache[n]){
return cache[n];
}
return cache[n] = fibonacci(n-1) + fibonacci(n-2);
}
fibonacci(tesetNum);
console.timeEnd('HasCache');
// 輸出
// NoCache: 1717.834ms
// HasCache: 0.159ms
通過(guò)性能測(cè)試可以看到喂江，當(dāng)測(cè)試數(shù)是40時(shí)不適用緩存消耗的時(shí)間就是使用緩存的1700多倍(好可怕的數(shù)據(jù))召锈，我試了下當(dāng)測(cè)試數(shù)據(jù)是300時(shí)，开呐，烟勋，，筐付，卵惦，，瓦戚，我就等不急它的執(zhí)行了沮尿。
使用場(chǎng)景
當(dāng)遞歸調(diào)用里有大量重復(fù)計(jì)算的情景，或者組件较解、數(shù)據(jù)等重復(fù)加載的情況下畜疾，使用緩存是個(gè)不錯(cuò)的選擇(典型的以空間換時(shí)間)
