带有回忆的尾部回复POW（）算法？

Question

我正在寻找一种计算 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 的结果。

Answer 1

如果您使用 SICP 第 1.2.4 节求幂。它不使用记忆，但一般方法是 O(log n) 而不是 O(n)，因此您仍然应该看到改进。

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

Answer 2

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

我认为你需要有一个 (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，它缓存的内容与它应该计算的内容完全不同。

Answer 3

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

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 - 来存储已经计算出的值。