_。momoize不会提高性能

Question

考虑发现第n个斐波那契数。原始功能fib(32)和_.memoize(fib)(32)占用相同的时间。

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

您会看到两者大致花费相同的时间。 无性能改进。是否有方法可以更改memoize函数以创建一个真正的备注，该备注等同于在fib本身内部实现备注？再说一遍，我希望性能与以下相同：

// 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]
}

Answer 1

第一次运行它不会更快。记忆只会给您后续执行带来的好处。

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

这给了我：

with memo: 0.0732421875ms
no memo: 25.131103515625ms

Answer 2

您遇到的问题是_.memoize实际上并未更改传入的函数，而是对其进行了包装。递归时，您正在调用的是原始函数，而不是包装函数，因此您无法在递归调用中获得备忘录的好处。您需要确保递归调用正在调用备注函数。一种方法是做类似的事情：

let fib_memo = _.memoize((num) => {
    if (num <= 1) return 1;
    // call the memoized version:
    return fib_memo(num - 1) + fib_memo(num - 2);
})

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

// fast
console.time('with memo')
let fm = fib_memo(32)
console.timeEnd('with memo')
console.log("fib:", fm)

// slow
console.time('with no memo')
let fnm = fib(32)
console.timeEnd('with no memo')
console.log("fib:", fnm)

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>