JavaScript记忆化

Question

请问有没有人能提供一个仅使用Javascript的简单记忆功能函数？我在谷歌上搜索时找到了一些文章，但是并没有很多关于这个的内容。我找到的最好的文章是这篇：http://alivedise.github.io/blog/2012/12/22/javascript-memorization/。我明白缓存是什么，但是这个例子对我来说太复杂了。我希望这里的任何人都可以提供一个简单的函数和调用，这样我就可以开始更深入地理解它了。谢谢。

- user2956271

---

这种技术的名称实际上是“记忆化”。在谷歌上搜索可能会带来更多结果。 - Martin Smith

好的，现在开始做。谢谢你的输入，马丁。 - user2956271

Answer 1

我认为你所需要的是“记忆化”。

来自维基百科：

记忆化是一种优化技术，主要用于通过让函数调用避免重复计算先前处理过的输入的结果来加速计算机程序。

这里有一篇不错的文章这里和另一个SO问题这里。

通常使用记忆化来减少反复计算总是相同的结果的成本。任何性能改进都是以为缓存结果分配内存为代价的。

以下是代码中的简单示例：

var cachedResult;
function doHeavyCalculation()
{
    if (typeof(cachedResult) !== 'undefined')
        return cachedResult;

    // no cached result available. calculate it, and store it.
    cachedResult = /* do your computation */;
    return cachedResult;
}

有一些支持记忆任何函数的JavaScript框架，它们基本上通过装饰一个函数为您提供可重用的样板代码。

- Drew Noakes

---

嗨，Drew，我看到了那篇文章。感谢你提供的SO示例，这个对我帮助很大！ - user2956271

我认为这个答案可以改进。目前看来，你假设函数每次返回相同的值（如果cachedResult未定义，则将值分配给变量，否则从变量获取它），而“/进行计算/”则需要想象力。 - user10706046

@ArturTagisow 备忘录技术就是这个意思：为给定的参数列表返回相同的结果。在此示例中，没有参数，所以缓存只是一个单一值。如果您有一个参数列表，则内存/缓存将需要考虑到这一点。 - Drew Noakes

Answer 2

我想你是指“记忆化”，它基本上意味着记住你已经计算过的内容。以下是一种使用记忆化的斐波那契算法。

var cache = {1:1, 2:1};
function fib(n) {
    if(!cache[n]) // Have we already calculated this value?
       cache[n] = fib(n - 1) + fib(n - 2)  // Calculate and store it

    return cache[n]
}

- keslert

Answer 3

恐怕其他答案都使用全局变量，这是错误的。JavaScript 提供了更好的解决方案。请注意函数表达式后面的括号 ()。它意味着该函数立即执行，并且由该函数返回的结果（并分配给 memo 常量）是另一个函数，该函数进行计算本身，但可以使用已执行函数上下文中的变量缓存作为变量。缓存仅可由 memo 函数访问。

const memo = function () {
  let cache = [];
  return function (n) {
    if (cache.includes(n)) { console.log("already in memory") }
    else { console.log("first"); cache.push(n); }
  }
}();

memo(7) //first
memo(7) //already in memory
memo(7) //already in memory
memo(1) //first
memo(1) //already in memory

- Tomas Bruckner

Answer 4

keslert 的 Fibonacci 示例是一个很好的例子，这里再举一个使用编辑距离作为示例来帮助你理解。

// Map<string, Map<string, number>>
const cache = new Map();

// a: string, b: string
function editDistance(a, b) {
    if (a.length === 0) {
        return b.length;
    }
    if (b.length === 0) {
        return a.length;
    }
    let res = cache.getMap(a).get(b);
    if (res !== undefined) {
        return res;
    }
    res = Math.min(
        editDistance(pop(a), pop(b)) + (last(a) === last(b) ? 1 : 0)
        , editDistance(pop(a), b) + 1
        , editDistance(a, pop(b)) + 1
    );
    cache.getMap(a).set(b, res);
    return res;
}

值得一提的是，在某些情况下，直接计算比查找内存（缓存）更省成本。例如基本逻辑操作或几步数学运算。

要详细确定确切的情况，您需要了解缓存使用的机制（数据结构、操作复杂度，甚至存储介质（即您是否使用快速RAM还是交换到慢速硬盘？）），这取决于浏览器/JavaScript引擎的实现。

来源：https://github.com/beenotung/programming-class/blob/3f678ac48511d829149fb06c139e53cc2680ae82/edit-distance/edit-distance.ts -- 编辑 2018年3月6日13:56

在此示例中，对pop / 1函数的调用也可以被缓存。

- Beeno Tung