memoized 函数

知道算法里的动态规划不?

动态规划 动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，其经过分解的子问题往往不是相互独立的

• 其解依赖于子问题

• 子问题的求解是重复的

• 采用重递归出现的大量重复运算

如 Fib 数列 采用动态规划方法

• 构造所有子问题的一个表格

• 采用自底向上的方法依次求解子问题

• 也可以采用自上而下，为避免重复运算，采用 备忘录 或称为 记忆递归

memoized函数使得函数能够记住其计算结果,避免大量重复计算.

_.memoized = (fn,hasher) => {
      //这里依旧利用闭包可以记录上下文的特性
        const lookupTable = {};

        return (key)=>{
                //为了应对多个参数的情况,可接受传入hasher自定义对象的key
                var address = hasher ? hasher.apply(this,arguments) : key;

                return lookupTable[address] || (lookupTable[address] = fn(address));
        }
}

示例:

let fc = _.memoized((n)=>{
    if(n===0){
        return 1;
    }
    return n*fc(n-1);
})

console.time(1)
console.log(fc(10));//3628800
console.timeEnd(1);//3.876ms

console.time(2);
console.log(fc(11));//39916800
console.timeEnd(2);//0.896ms