CODEWITHSUNDEEP
javascriptnode.jsunderscore.jslodashmemoization
Maria
Maria

Reputation: 3525

_.memoize does not increase performance

Consider the finding nth Fibonacci number. The raw function fib(32) and _.memoize(fib)(32) take the same time. 

function fib(num) {
    if (num <= 1) return 1;
    return fib(num - 1) + fib(num - 2);
}

// slow
console.time('with memo')
_.memoize(fib)(32)
console.timeEnd('with memo')

// slow
console.time('no memo')
fib(32)
console.timeEnd('no memo')

You'll see both take roughly the same time. No performance improvement. Is there a way to alter the memoize function to create a true memoization that's equivalent to implementing memoization inside fib itself? Aka, I want the performance to the same as:

// true memoization, actual performance improvement
// very fast!
cache = {}
function fib(n) {
    if (!cache[n]){
        if (n <= 1) cache[n] = 1;
        else cache[n] = fib(n - 1) + fib(n - 2);
    }
    return cache[n]
}

Upvotes: 0

Views: 164

Answers (1)

d4nyll
d4nyll

Reputation: 12627

It's not going to be faster the first time you run it. Memoization only gives you the benefits on subsequent executions.

function fib(num) {
    if (num <= 1) return 1;
    return fib(num - 1) + fib(num - 2);
}

const fibmem = _.memoize(fib);

fibmem(32);
console.time('with memo')
fibmem(32);
console.timeEnd('with memo')

fib(32);
console.time('no memo')
fib(32)
console.timeEnd('no memo')

This gave me:

with memo: 0.0732421875ms
no memo: 25.131103515625ms

Upvotes: 1

Related Questions