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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (70)

我感兴趣的是我们有一些函数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并存储结果,然后将值传递给它所在的位置通常去。但我不知道该怎么做(这听起来很不愉快)。

提问于
用户回答回答于

可以访问JavaScript源代码。因此,我们可以尝试为memoized函数生成新的源代码。

function memo(f){
  const fName = new RegExp(f.name, 'g');
  const fCode = String(f).replace(/[^\(]+/,'')
    .replace(fName, 'g')
    .replace(/return/g, 'return cache[key] =')
    .replace(/{/, `{\n  const key = JSON.stringify(Array.from(arguments));\n\n  if (cache[key])\n    return cache[key];\n`);
  
  const code = 'function(){\nconst cache = {};\n\nfunction g' + fCode + '\n\nreturn g.apply(g, arguments);}'

  return Function('"use strict";return ' + code)();
}

function fib(n) {
  if (n <= 1) return 1;

  return fib(n - 1) + fib(n - 2);
}

const g = memo(fib);

console.log(g(100));
console.log(String(g));
用户回答回答于

我可能想要一个相同功能的memoized和非memoized版本然后我必须写两次相同的功能

是的,你需要。fact(n - 1)对函数内部的递归调用只能引用一个fact函数 - memoized或unmemoized函数。

因此,为了避免代码重复,您需要做的是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);

扫码关注云+社区

领取腾讯云代金券