2

我正在寻找一种算法来计算pow()尾递归并使用记忆来加速重复计算。

性能不是问题；这主要是一项智力练习——我花了一趟火车，pow()想出了我能想到的所有不同的实现，但无法想出一个我满意的具有这两个属性的实现。

我最好的镜头如下：

def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0):
    if exp == 0:
        return 1
    elif exp == 1:
        return acc * base
    elif exp in cache_line:
        val = acc * cache_line[exp]
        cache_line[exp + ctr] = val
        return val
    else:
        cache_line[ctr] = acc        
    return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1)

它可以工作，但它不会记住所有计算的结果 - 只有那些具有指数1..exp/2和exp.

4

3 回答 3

2

如果您使用SICP 第 1.2.4 节中描述的连续平方技术，您将获得更好的性能。它不使用记忆，但一般方法是 O(log n) 而不是 O(n)，所以你应该仍然看到改进。

我在这里讨论练习 1.16 中迭代过程的解决方案。

于 2010-04-04T17:45:40.730 回答
0

我不认为您在缓存中记录了正确的内容，当您使用不同的参数调用它时，映射发生了变化。

我认为您需要缓存（base，exp）-> pow（base，exp）。

我明白这ctr是为了什么，以及为什么只记录了您期望的一半。

考虑calc_tailrec_mem(2,4)：第一层，pow(2,1) 记录为 2，下一层 = calc_tailrec_mem(2,3,...)，pow(2,2) 被记录。下一级是calc_tailrec_mem(2,2,...)，但它已经保存在缓存中，因此递归停止。

该函数非常令人困惑，因为由于累加器和ctr.

于 2010-04-04T17:59:44.927 回答
0

这太晚了，但是任何人都在寻找答案，这里是：

int powMem(int base,int exp){
    //initializes once and for all
    static map<int,int> memo;

    //base case to stop the recursion
    if(exp <= 1) return base;

    //check if the value is already calculated before. If yes just return it.
    if(memo.find(exp) != memo.end())
        return memo[exp];

    //else just find it and then store it in memo for further use.
    int x = powMem(base,exp/2);
    memo[exp] = x*x;

    //return the answer
    return memo[exp];
}

这使用 memo 数组 - 准确地说是一个 map - 来存储已经计算的值。

于 2017-05-25T06:51:30.203 回答