为递归算法添加一个记忆

Question

我已经编写了一个用于对数字进行分区的函数：

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);
}

在第二步中，我想给这个算法添加一个记忆，但无法想出正确的方式来实现它，因为直到最后都没有返回语句（当指定了返回时，例如在faactoral或fibbinacci中，我可以添加记忆）。有人能开车送我到正确的方向吗？

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

Answer 1

这里有一个更简单的代码：

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);
}

它使用众所周知的递推式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的所有分区的数目。

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

Answer 2

我会沿着以下路线：

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 3

根据您的其他需求，您可能需要考虑使用underscore.js，它有自己的_.memoize函数。

记忆的秘密在于它利用了闭包的工作方式。当您在另一个范围内定义一个函数时，它可以访问该范围内的所有内容。当您将该函数返回到作用域之外的某个位置时，它会引用作用域内可以看到的所有内容。

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

你的代码看起来像这样：

/**
 * 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));