Wie kann ich diese große faktorielle Funktion in eine Funktion höherer Ordnung umwandeln?

Question

Der folgende Code verwendet ein Objekt cache außerhalb der factorial-Funktion. Die factorial-Funktion selbst ist groß, was zu viele Bedenken hat, faktoriell und Caching zu finden.

Wie kann ich konvertieren diesen Code in eine Funktion höherer Ordnung und das gleiche Ergebnis erzeugen, wenn ich

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

Answer 1

nennen ist es schon other answers out there for memoising recursive functions, aber ich werde passen Sie diese Antwort auf factorial in Javascript an, damit Sie sehen können, wie es einfacher funktioniert

Das Geheimnis zum Schreiben von Memo-rekursiven Funktionen ist der Continuation-Passing-Stil. Eine ähnliche Technik funktioniert, wenn Sie eine nicht-tail-rekursive Funktion stack-safe machen wollen.

Ich werde einige console.log Anweisungen in diesem ersten Beispiel lassen, damit Sie sehen können, wann es tatsächlich rechnet und wenn es nur eine Memo-Suche macht.

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

---

Hier habe ich die console.log Anrufe innerhalb von memoise entfernt und stattdessen eine memoised Fibonacci-Funktion vs einem unmemoised ein demonstrieren. Vergleichen Sie die dramatische Zeitdifferenz zwischen memoise(fibk) und 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')