Javascript记忆

Question

有人可以使用Javascript提供一个简单的记忆功能。我在网上搜索时发现了一些文章，但我没有看到很多。我找到的最好的文章是这个：

http://alivedise.github.io/blog/2012/12/22/javascript-memorization/

我理解缓存是什么，但这个例子对我来说太复杂了。我希望这里的任何人都可以提供一个简单的功能和电话，以便我可以接受并开始更深入地理解这一点。

谢谢

Answer 1

我认为你要找的是备忘录。

来自Wikipedia：

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

有一篇很好的文章here和另一个SO问题here。

您通常使用memoization来降低重复计算始终相同的结果的成本。任何性能改进都是以为缓存结果分配内存为代价的。

代码中的一个简单示例：

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框架支持memoizing任何函数，它们基本上通过装饰函数以可重用的方式为您提供这个样板代码。

Answer 2

我认为你的意思是记忆，这基本上意味着记住你已经计算过的东西。以下是使用memoization的Fibonacci算法。

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]
}

Answer 3

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函数的调用。