javascript - 如何使这个高阶内存函数适用于递归函数？

Question

我有一个基本的内存功能，写为

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

它不适用于递归调用自身的函数。例如:

const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci)
memoizedFib(20)

在斐波那契内部，它仍然进行大量重复计算。

我想避免这种情况的一种方法是将内存插入到函数的实现中。

const cache = new Map();
const memoFibonacci = (n) => {
  if (memory.has(n)) return memory.get(n);
  if (n <= 1) return 1;
  const result = memoFibonacci(n - 1) + memoFibonacci(n - 2);
  memory.set(n, result);
  return result;
};

我想知道是否有一种方法可以使高阶 util 函数与斐波那契等递归函数一起使用？

Answer 1

这是一个非内存递归函数作为基准:

const fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const result = fibonacci(5);

console.log("result:", result);

.as-console-wrapper { max-height: 100% !important }

直接定义内存函数

您可以定义函数和内存，这将使所有递归调用都使用内存版本:

看起来如何

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

const result = fibonacci(5);

console.log("result:", result);

.as-console-wrapper { max-height: 100% !important }

用内存替换原来的

您也可以稍后通过替换其原始绑定(bind)来内存它。为此，该函数不应定义为 const。这仍然会使将来的调用使用内存版本:

看起来如何

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

或者

function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

.as-console-wrapper { max-height: 100% !important }

---

警告

请注意，这仅适用于引用您可以控制的绑定(bind)的递归函数。并非所有递归函数都是这样。几个例子:

命名函数表达式

例如，如果函数使用本地名称定义，则只有该函数可以使用该名称来引用自身:

看起来如何

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

.as-console-wrapper { max-height: 100% !important }

这是因为函数表达式的名称可以在函数体内使用，并且不能从外部覆盖。实际上，它与制作它是一样的:

let fibonacci = function recursive(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return recursive(n - 1) + recursive(n - 2)
};

fibonacci = memo(fibonacci);

内部函数

它也不适用于使用内部递归助手的函数:

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);

.as-console-wrapper { max-height: 100% !important }

模块/其他范围

如果您无权访问该函数的定义，那么您就无法真正控制它用于调用自身的绑定(bind)。使用模块时最容易看到:

看起来如何

斐波那契.js

export let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

index.js

import { fibonacci as fib } from "./fibonacci.js"

//assume memo() exists here

let fibonacci = memo(fib);
fibonacci(5);

这不会影响递归函数，因为它仍然从模块范围引用自身。