帶記憶的尾遞歸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（）算法？

回答

相關問題