函数记忆

什么是函数记忆？

• 函数记忆是一种编程技巧,通过牺牲算法的空间复杂度以换取更优的时间复杂度

函数记忆的实现

• 向memorize函数中传入目标函数，返回一个新的函数，新函数执行多次 ，若参数一致,则通过缓存读取存取计算结果，实现函数记忆的效果
• 需求： 计算25的阶乘

function factorial(n) {  // 定义一个递归阶乘函数
  if (n == 0 || n == 1) {
    return 1
  } else {
    return n * factorial(n - 1)
  }
}

// 记忆函数
function memorize(fn) {
  let cache = {}
  return function () {
  let key = JSON.stringify(arguments);
  if (cache[key]) {
    return cache[key]
  } else {
    cache[key] = fn.apply(this, arguments)
    return cache[key]
    }
  }
}

• 测试

let newFn = memorize(factorial)
  console.time("1")
  console.log(factorial(25))
 console.timeEnd("1")

  console.time("2")
  console.log(newFn(25))
  console.timeEnd("2")

  console.time("3")
  console.log(newFn(25))
  console.timeEnd("3")

  console.time("4")
  console.log(newFn(25))
  console.timeEnd("4")

image.png

• 第三、四次执行的是从缓存中获取结果，时间明显短了

注意:

• 函数记忆适用于大量重复计算的场景
• 如果不存在大量可能的重复计算,使用函数记忆会让计算更加低效

END