2

以下代碼使用factorial函數之外的cache對象。函數本身很大,對尋找階乘和緩存有太多顧慮。如何將此大因子函數轉換爲更高階的函數?

我怎麼能這樣的代碼轉換爲高階函數併產生相同的結果時,我打電話

console.log(factorial(5)); 
console.log(factorial(7)); 

cache = { } 
 

 
function factorial(n) { 
 
    
 
    if (n === 0) { 
 
    return 1; 
 
    } 
 
    
 
    if (cache[n]) 
 
    { 
 
    return cache[n]; 
 
    } 
 
    
 
    console.log("Stack Up: " + n); 
 
    
 
    var value = n * factorial(n - 1); 
 
    
 
    console.log("Stack Down: " + value); 
 
    
 
    cache[n] = value; 
 
    
 
    return value; 
 
} 
 

 
console.log(factorial(5)); 
 
console.log(factorial(7));

+1

這樣的高階函數通常被稱爲* memoize的* /記憶化是Google保持着良好的關鍵字的巨大時間差。 – stholzm

+1

看看[這些例子](http://stackoverflow.com/a/22578970/1048572) – Bergi

回答

1

有已經other answers out there for memoising recursive functions,但我會在javascript中將這個答案調整爲階乘,這樣你就可以更容易地看到它是如何工作的

寫回憶遞歸函數的祕訣是繼續傳遞樣式。當你想使非尾遞歸函數堆棧安全時,類似的技術就可以工作。

我會在第一個示例中留下一些console.log聲明,以便您可以看到它何時實際正在計算以及何時只是進行備忘錄查找。

const memoise = f => { 
 
    const memo = new Map() 
 
    const compute = (x, k) => 
 
    (console.log('compute', x), 
 
    memo.get(x, memo.set(x, f(x,k)))) 
 
    const lookup = x => 
 
    (console.log('lookup', x), 
 
    memo.has(x) ? memo.get(x) : compute(x, lookup)) 
 
    return lookup 
 
} 
 

 
const factk = (x, k) => { 
 
    if (x === 0) 
 
    return 1 
 
    else 
 
    return x * k(x - 1) 
 
} 
 

 
const memfact = memoise(factk) 
 

 
console.log(memfact(5)) // 120 
 
console.log(memfact(7)) // 5040


在這裏,我已經刪除的memoiseconsole.log電話,而是表現出memoised斐波那契功能VS的unmemoised之一。比較memoise(fibk)badfib之間

const memoise = f => { 
 
    const memo = new Map() 
 
    const compute = (x, k) => 
 
    memo.get(x, memo.set(x, f(x,k))) 
 
    const lookup = x => 
 
    memo.has(x) ? memo.get(x) : compute(x, lookup) 
 
    return lookup 
 
} 
 

 
const fibk = (x, k) => { 
 
    if (x < 2) 
 
    return x 
 
    else 
 
    return k(x - 1) + k(x - 2) 
 
} 
 

 
const badfib = x => { 
 
    if (x < 2) 
 
    return x 
 
    else 
 
    return badfib(x - 1) + badfib(x - 2) 
 
} 
 

 
console.time('memoised') 
 
console.log(memoise (fibk) (35)) // 9227465 1.46ms 
 
console.timeEnd('memoised') 
 

 
console.time('unmemoised') 
 
console.log(badfib(35))   // 9227465 135.85ms 
 
console.timeEnd('unmemoised')

+1

我們可以進一步使用部分應用程序 - 'fibk = k => x => ...' – Bergi

+0

我不是看看部分應用程序在這個時候會有所幫助...請給我看!^_^ – naomik

+0

也許這並沒有多大幫助,但'const lookup = x =>(memo.has(x)?memo:memo.set(x,comp(x)))。get(x); const comp = f(lookup);' – Bergi