這個C++函數如何使用記憶？

#include <vector> 
std::vector<long int> as; 

long int a(size_t n){ 
    if(n==1) return 1; 
    if(n==2) return -2; 
    if(as.size()<n+1) 
    as.resize(n+1); 
    if(as[n]<=0) 
    { 
    as[n]=-4*a(n-1)-4*a(n-2); 
    } 
    return mod(as[n], 65535); 
}

上面的代碼示例使用記憶來計算基於一些輸入n的遞歸公式。我知道這使用memoization，因爲我已經寫了一個純粹的遞歸函數，它使用相同的公式，但是這對於更大的值n要快得多。我以前從未使用過載體，但我已經做了一些研究，並且瞭解它們的概念。我知道memoization應該存儲每個計算的值，以便不再執行相同的計算，而是可以簡單地檢索已經計算的值。這個C++函數如何使用記憶？

我的問題是：這是怎麼記憶化，以及它是如何工作的？我似乎無法在代碼中看到它檢查n的值是否已經存在。另外，我不明白if(as[n]<=0)的目的。這個公式可以產生正面和負面的價值，所以我不確定這張支票正在尋找什麼。

謝謝，我想我已經接近了解它是如何工作的，它實際上比我想象的要簡單一些。

我不認爲序列中的值都不能爲0，所以這應該爲我工作，因爲我認爲n具有在1

但是開始，如果零在我的序列號可行，我能以另一種方式解決它？例如，如果五個永遠不會出現？我只需要用五個人來填充我的矢量？

編輯：哇，我得到了很多的其他的反應，同時檢查代碼並輸入這一個。感謝大家的幫助，我想我現在明白了。

來源

2008-09-29 Zachary Wright

if (as[n] <= 0)是支票。如果有效值可以像你說的那樣是負值，那麼你需要一個不同的哨兵來檢查。有效值可以爲零嗎？如果不是，那麼只需進行測試if (as[n] == 0)。這使得您的代碼更容易編寫，因爲默認向量int s被零填充。

來源

2008-09-29 03:08:31

如果公式可以產生正的和負的值，則此函數具有一個嚴重的錯誤。檢查if(as[n]<=0)是假定要檢查它是否已經緩存了這個計算值。但如果公式可以是負數，這個函數重新計算這個緩存值很多...

它真的可能想要的是一個vector<pair<bool, unsigned> >，其中布爾說，如果該值已經計算或沒有。

來源

2008-09-29 03:30:23

該代碼似乎錯誤地檢查是（如[n] < = 0），並重新計算該函數的負值（似乎是大約每隔一個值）。這使得工作的規模與遞歸解決方案中的n而不是2^n成線性關係，因此運行速度更快。

不過，更好的檢查將是測試如果（如[N] == 0），這似乎運行3倍我的系統上更快。即使函數可以返回0，0值也只是意味着計算時間稍長一些（儘管如果0是一個頻繁的返回值，您可能需要考慮一個單獨的向量來標記該值是否已經被計算，而不是使用單個向量來存儲該函數的值以及它是否已被計算的）

來源

2008-09-29 03:36:01 Plasmer

我認爲當檢查結果爲[n] <= 0時，只需要較小的基數，它仍然需要指數時間。確實，計算一個（10000） - 它將永遠不會完成，即使它沒有花時間進行正確的檢查。 – 2008-09-29 03:45:17

的代碼，作爲貼，僅memoizes的時間（精確地，當記憶值爲正）約40％。正如Chris Jester-Young所指出的那樣，正確的實施將會改爲檢查if(as[n]==0)。另外，可以改變記憶化代碼本身讀取as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

（即使是==0檢查將花力氣當memoized值爲0。幸運的是，你的情況，這永遠不會發生！）

來源

2008-09-29 03:38:18

有一個錯誤這段代碼。它將繼續重新計算as [n]的值，因爲[n] < = 0。它將記憶一個結果爲正值的值。它的工作速度比沒有備忘錄的代碼快很多，因爲as []有足夠的正值，所以遞歸很快結束。你可以通過使用一個大於65535的值作爲信號來改善這一點。當矢量展開時，矢量的新值被初始化爲零。

來源

2008-09-29 04:20:16

這個C++函數如何使用記憶？

回答

相關問題