說明

這是在codewars.com上刷的一道js練習題，在此做個記錄

問題描述

The Fibonacci sequence is traditionally used to explain tree recursion.

斐波那契序列通常是用來解釋遞歸調(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)).

這個算法以教學為目的,但非常低效的,不僅因為遞歸,而且兩次調(diào)用fibonacci函數(shù),在函數(shù)里面右側(cè)調(diào)用的fibonacci(n-2) 在表達式左側(cè)調(diào)用fibonacci(n-1)時就已完全計算過一遍。

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.

這個算法效率是如此之低,斐波納契數(shù)超過50的實在太多了。你可以去喝杯咖啡或去睡午覺時等待答案。但如果你就用這個代碼在codewars上很可能得到一個超時錯誤。

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.

對于這個特定卡塔(類似打怪升級里面的級數(shù))，我們想實現(xiàn)緩存的解決方案。這是特別酷的,因為它將讓我們繼續(xù)使用遞歸算法,同時仍然保持足夠迅速的得到一個答案。

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的版本的訣竅是,保持一個緩存數(shù)據(jù)結(jié)構(gòu)(最有可能的關(guān)聯(lián)數(shù)組),將斐波納契數(shù)列的值緩存。當獲取一個斐波那契數(shù)列值時,首先在緩存中查找，如果有則直接返回值,如果沒有,再計算并把它放進緩存。

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，那么需要計算69和68的值。
在計算69的過程中又計算了 68、67、、、、、1。 計算 68的過程又計算了 67、66、、、、、、、1的值，如此重復(fù)計算的值太多了，花費的時間也就比較多。

緩存思想恰好可以減少不必要的重復(fù)計算。當?shù)谝槐橛嬎?9的值時就遞歸計算了 68、67、66、、、1的值，之后的每次都先查看是否有緩存，有就直接返回緩存值，避免了重復(fù)計算。

代碼

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);
}

性能測試

//沒有緩存時
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');

// 使用緩存時
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

通過性能測試可以看到，當測試數(shù)是40時不適用緩存消耗的時間就是使用緩存的1700多倍(好可怕的數(shù)據(jù))，我試了下當測試數(shù)據(jù)是300時，，，，，，，，我就等不急它的執(zhí)行了。

使用場景

當遞歸調(diào)用里有大量重復(fù)計算的情景，或者組件、數(shù)據(jù)等重復(fù)加載的情況下，使用緩存是個不錯的選擇(典型的以空間換時間)