在JavaScript中记忆任何给定的递归函数

Question

我感兴趣的是我们有一些函数f的场景,它是递归的,我们没有提供源代码.

我想要一个函数memoizer:Function - > Function,它接受说f并返回一个函数g,使得g = f(在某种意义上它们返回给定相同参数的相同值),当调用时首先检查被调用的参数是否为在它的'缓存'(它之前已经计算过的结果的内存)中,如果这样返回结果,否则它应该计算f,如果f用一些参数调用自己,这无异于用这些参数调用g,我想首先检查g的缓存是否包含这些参数,如果是,则返回结果,否则......

这很容易(在Javascript中)给出f的源代码,我只是以明显的方式定义memoize并做类似的事情

let f = memoize((...args) => {/* source code of f */});

但这根本不吸引我(主要是因为我可能想要一个相同功能的memoized和非memoized版本然后我必须写两次相同的功能)如果我不知道将无法工作如何实施f.

如果我不清楚我在问什么,

我想要一个函数memoize,它具有如下函数

fact = n => n === 0 ? 1 : n * fact(n - 1);

并且返回一些新函数g,使得所有n的fact(n)= g(n)并且例如当计算g(10)时存储fact(0),...,fact(10)的值,这是计算g(10)时计算,然后如果我要求说g(7)它在缓存中找到结果并将其返回给我.

我认为概念上可以检测f何时被调用,因为我有它的地址,也许我可以用一个新函数替换所有对f的调用,我计算f并存储结果,然后将值传递到它所在的位置通常去.但我不知道该怎么做(这听起来很不愉快).

Answer 1

我可能想要同一函数的记忆化和非记忆化版本，然后我必须编写相同的函数两次

是的，你需要这样做。函数内部的递归调用fact(n - 1)只能引用一个fact函数 - 可以是已记忆的函数，也可以是未记忆的函数。

因此，为了避免代码重复，您需要做的是fact使用Y 组合器定义：

const makeFact = rec => n => n === 0 ? 1 : n * rec(n - 1);
//               ^^^                           ^^^

const factA = Y(makeFact);
const factB = memoizingY(makeFact);

function Y(make) {
    const f = make((...args) => f(...args)); // const f = make(f) is easier to understand
    return f;                                // but doesn't work with eager evaluation
}

我将把 的定义留给memoizingY读者作为练习:-)

可能更简单的方法：

const makeFact = annotate => {
    const f = annotate(n => n === 0 ? 1 : n * f(n - 1));
    return f;
}

const factA = makeFact(identity);
const factB = makeFact(memoize);

Answer 2

也许我可以用一个新函数替换对 f 的所有调用，在该函数中计算 f 并存储结果，然后将值传递到通常所在的位置。

正如 Bergi 在评论中提到的那样，这实际上很容易做到。

// https://stackoverflow.com/questions/24488862/implementing-automatic-memoization-returns-a-closured-function-in-javascript/ 
function memoize(func) {
  var memo = {};
  var slice = Array.prototype.slice;

  return function() {
    var args = slice.call(arguments);

    if (args in memo)
      return memo[args];
    else
      return (memo[args] = func.apply(this, args));

  }
}

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

fib = memoize(fib);

console.log(fib(100));