带记忆的尾递归pow（）算法？

我正在寻找一种算法来计算pow()这是尾递归，并使用memoization加快重复计算。带记忆的尾递归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)

它的工作原理，但它并不memoize的所有计算的结果 - 只有那些具有指数1..exp/2和exp。

来源

2010-04-04 Dan

它是记忆而不是记忆：http://en.wikipedia.org/wiki/Memoization – hobodave 2010-04-04 17:30:04

哇，这是Python的默认参数的可怕使用。你实际上在那里模拟一个全局变量。 – Thomas 2010-04-04 17:38:25

我不认为你在缓存中记录正确的东西，当你用不同的参数调用映射时，映射会改变。

我想你需要有一个缓存（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,...)，但它已保存在缓存中，因此递归停止。

由于acculumator和ctr，该函数非常容易混淆，因为它缓存了与它应该计算的内容完全不同的内容。

来源

2010-04-04 17:59:44

你对前两点是正确的;代码中的记录是exp - > pow（base，exp） - 在其他地方有一些代码可以跟踪基础并确保计算记录在正确的位置。 – Dan 2010-04-04 18:09:18

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

我从练习1.16 here谈到迭代过程的解决方案。

来源

2010-04-04 17:45:40

我并没有在市场上表现出来（或者在任何真实情况下使用它） - 这是一个有点任意的挑战，我自己决定我无法找出答案。 – Dan 2010-04-04 17:51:18

这是太晚，但没有人在那里寻找答案，那就是：

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

这里使用了备忘录阵列 - 地图，准确的说 - 存储已经计算出的值。

来源

2017-05-25 06:51:30 Nuhman

带记忆的尾递归pow（）算法？

回答

相关问题