向递归算法添加记忆

Question

我已经为partitioning a number写了一个函数：

var combinations = function (i) {
    var mem = [];
    function inner(n, r, m) {
        for (var k = m; k <= n; k++) {
            if (k == n) {
                r.push(k);
                mem[r] = 1;

                return mem;
            }
            else {
                var copy = r.slice(0);
                copy.push(k);
                inner(n - k, copy, k);
            }
        }
    }

    return inner(i, [], 1);
}

在第二步中，我想为该算法添加一个记忆，但想不出正确的实现方式，因为直到最后都没有 return 语句（当 return 是指定的，例如在 faactorial 或 fibbinacci 中我可以添加记忆）。谁能给我指引正确的方向？

[编辑] 我需要这个算法尽可能快。这是 codewars 的 kata 竞赛：link 要求它必须在 6000ms 以下执行，输入高达 330。这是我能想到的最好的算法，除了如何存储部分结果。

Answer 1

我会遵循：

var cache = {};

var combinations = function (i) {
    if ( cache[i] ){
        return cache[i];
    };

    var mem = [];
    function inner(n, r, m) {
        for (var k = m; k <= n; k++) {
            if (k == n) {
                r.push(k);
                mem[r] = 1;

                return mem;
            }
            else {
                var copy = r.slice(0);
                copy.push(k);
                inner(n - k, copy, k);
            }
        }
    }

    cache[i] = inner(i, [], 1);
    return cache[i];
}

但是您必须修改您的算法以利用它 cache（首先计算最大项？）

Answer 2

根据您的其他要求，您可能需要考虑使用具有 its own _.memoize function.

的 underscore.js

记忆的秘诀在于它利用了闭包的工作原理。当您在另一个范围内定义一个函数时，它可以访问该范围内的所有内容。当您 return 该函数作用于作用域外的某个地方时，它会引用它在作用域内可以看到的所有内容。

因此，要实现记忆，您需要创建一个函数，该函数 return 是另一个函数，该函数在调用内部函数之前进行记忆检查。

您的代码将如下所示：

/**
 * Because we'll be returning "a function that returns a function" below,
 * this needs to be executed immediately so combinations() is just
 * a standalone function.
 */
var combinations = (function(i) {

    /**
     * mem needs to stay outside the scope of your inner function.
     * If it's in a closure like this, JavaScript will keep its value
     * around as long as combinations still exists.
     */ 
    var mem = [];

    /**
     * A memoization wrapper should return a memoized function
     */
    return function(i) {

        /**
         * Check if mem[i] is set and return it if it has been
         */
        if(mem[i] !== undefined) {
            console.log('returning memoized value');
            return mem[i];    
        }

        function inner(n, r, m) {
            for (var k = m; k <= n; k++) {
                if (k == n) {
                    r.push(k);
                    mem[r] = 1;

                    return mem;
                }
                else {
                    var copy = r.slice(0);
                    copy.push(k);
                    inner(n - k, copy, k);
                }
            }
        }

        /**
         * If the value needs to be computed, we can set it at the same time
         * as we return it instead of putting it in a temporary variable.  
         */ 
        console.log('computed');
        return mem[i] = inner(i, [], 1);
    }

}()); /** <--- That's the rest of the automatic execution */

console.log(combinations(5));
console.log(combinations(5));

Answer 3

这是一个更简单的有效代码：

function nr_partitions(n) { return p(n, n); }

function p(sum,largest) {
    if (largest == 0) { return 0; }
    if (sum == 0) { return 1; }
    if (sum < 0) { return 0; }
    return p(sum, largest-1) + p(sum-largest, largest);
}

它使用了一个well-known recurrence，p(n,k) = p(n,k-1) + p(n-k, k)，其中p(n.k)表示n的分区数，其中最大部分最多为k（例如 p(3, 2)=2 因为我们只计算 1+1+1,1+2，而不是 3)。对于 k=n 我们得到 n.

所有分区的数量

添加 memozation 涉及存储字典映射对 (sum, largest) 到 p(sum, largest)。

向递归算法添加记忆

add a memoization to recursive algorithm

javascript

recursion

memoization