Memoize - 透過以空間換取時間來讓函式執行得更快
use Memoize;
memoize('slow_function');
slow_function(arguments); # Is faster than it was before這通常就是您需要知道的所有資訊。不過，還有許多選項可用
memoize(function, options...);選項包括
NORMALIZER => function
INSTALL => new_name
SCALAR_CACHE => 'MEMORY'
SCALAR_CACHE => ['HASH', \%cache_hash ]
SCALAR_CACHE => 'FAULT'
SCALAR_CACHE => 'MERGE'
LIST_CACHE => 'MEMORY'
LIST_CACHE => ['HASH', \%cache_hash ]
LIST_CACHE => 'FAULT'
LIST_CACHE => 'MERGE'Memoizing 函式會透過以空間換取時間來讓函式執行得更快。它會將函式的回傳值快取到一個表格中。如果您再次使用相同的引數呼叫函式，memoize 會介入並從表格中提供值，而不是讓函式重新計算值。
以下是一個極端的範例。考慮由下列函式定義的費氏數列
# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}這個函式非常慢。為什麼？要計算 fib(14)，它首先要計算 fib(13) 和 fib(12)，然後將結果相加。但是，要計算 fib(13)，它首先必須計算 fib(12) 和 fib(11)，然後再回來重新計算 fib(12)，即使答案是一樣的。而且，在它想要計算 fib(12) 的兩次中，它都必須從頭開始計算 fib(11)，然後在每次想要計算 fib(13) 時都必須再做一次。這個函式會重新計算太多舊結果，因此執行時間非常長---fib(14) 會對自己進行 1,200 次額外的遞迴呼叫，來計算和重新計算它已經計算過的內容。
此函數很適合用於記憶化。如果你記憶化上述的 fib 函數，它將只計算一次 fib(14)，也就是第一次需要時，然後將結果儲存在一個表格中。然後如果你再次要求 fib(14)，它將從表格中提供結果。在計算 fib(14) 時，它不會計算 fib(12) 兩次，而是只計算一次；第二次需要值時，它會從表格中取得。它不會計算 fib(11) 四次；它只計算一次，接下來的三次從表格中取得。它不會對 fib 進行 1,200 次遞迴呼叫，而是進行 15 次。這讓函數快了約 150 倍。
你可以透過重寫函數來自行進行記憶化，如下所示
# Compute Fibonacci numbers, memoized version
{ my @fib;
sub fib {
my $n = shift;
return $fib[$n] if defined $fib[$n];
return $fib[$n] = $n if $n < 2;
$fib[$n] = fib($n-1) + fib($n-2);
}
}或者你可以使用這個模組，如下所示
use Memoize;
memoize('fib');
# Rest of the fib function just like the original version.這讓開啟和關閉記憶化變得容易。
以下是一個更簡單的範例：我寫了一個簡單的射線追蹤器；程式會朝某個方向查看，找出它在看什麼，然後將該物件的 color 值（通常是像 red 這樣的字串）轉換成紅色、綠色和藍色的像素值，如下所示
for ($direction = 0; $direction < 300; $direction++) {
# Figure out which object is in direction $direction
$color = $object->{color};
($r, $g, $b) = @{&ColorToRGB($color)};
...
}由於圖片中的物件相對較少，因此只有少數顏色會被反覆查詢。記憶化 ColorToRGB 讓程式快了數個百分點。
此模組只輸出一個函數，memoize。此套件中的其他函數與你無關。
你應該說
memoize(function)其中 function 是你想要記憶化的函數名稱，或對它的參照。memoize 會傳回對函數的新記憶化版本的參照，或在發生非致命錯誤時傳回 undef。目前沒有非致命錯誤，但未來可能會有。
如果 function 是函數名稱，則 memoize 會隱藏舊版本，並在舊名稱下安裝新的記憶化版本，因此 &function(...) 實際上會呼叫記憶化版本。
您可以傳遞一些選用選項給 memoize，以稍微改變其行為方式。若要提供選項，請像這樣呼叫 memoize
memoize(function, NORMALIZER => function,
INSTALL => newname,
SCALAR_CACHE => option,
LIST_CACHE => option
);這些選項都是選用的；您可以包含其中一些、全部或不包含任何選項。
如果您提供一個函數名稱給 INSTALL，memoize 會在您提供的名稱下安裝新的 memoize 版本函數。例如，
memoize('fib', INSTALL => 'fastfib')將 fib 的 memoize 版本安裝為 fastfib；若沒有 INSTALL 選項，它會將舊的 fib 取代為 memoize 版本。
若要防止 memoize 在任何地方安裝 memoize 版本，請使用 INSTALL => undef。
假設您的函數如下所示
# Typical call: f('aha!', A => 11, B => 12);
sub f {
my $a = shift;
my %hash = @_;
$hash{B} ||= 2; # B defaults to 2
$hash{C} ||= 7; # C defaults to 7
# Do something with $a, %hash
}現在，呼叫函數如下所示，它們完全等效
f(OUCH);
f(OUCH, B => 2);
f(OUCH, C => 7);
f(OUCH, B => 2, C => 7);
f(OUCH, C => 7, B => 2);
(etc.)但是，除非您告訴 Memoize 這些呼叫是等效的，否則它不會知道，它會分別計算函數調用的這些值，並將它們分別儲存。
若要防止這種情況，請提供一個 NORMALIZER 函數，將程式引數轉換成字串，等效引數會轉換成相同的字串。f 的 NORMALIZER 函數可能如下所示
sub normalize_f {
my $a = shift;
my %hash = @_;
$hash{B} ||= 2;
$hash{C} ||= 7;
join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
}上述的每個引數清單都來自 normalize_f 函數，看起來完全相同，如下所示
OUCH,B,2,C,7您會告訴 Memoize 使用這個正規化器，方式如下
memoize('f', NORMALIZER => 'normalize_f');memoize 知道，如果兩個引數清單的正規化版本相同，則它可以安全地查詢它為一個引數清單計算的值，並將其作為使用另一個引數清單呼叫函數的結果傳回，即使引數清單看起來不同。
預設正規化器只是將引數與字元 28 串接在一起。（在 ASCII 中，這稱為 FS 或控制-\。）這對於只有一個字串引數的函數總是正確運作，而且當引數從不包含字元 28 時也是如此。但是，它可能會混淆某些引數清單
normalizer("a\034", "b")
normalizer("a", "\034b")
normalizer("a\034\034b")例如。
由於雜湊鍵是字串，預設正規化器不會區分 undef 和空字串。當函數的引數是參考時，它也不會運作。例如，考慮一個函數 g，它取得兩個引數：一個數字和一個數字陣列的參考
g(13, [1,2,3,4,5,6,7]);預設正規化器會將其轉換成類似 "13\034ARRAY(0x436c1f)" 的內容。這沒問題，但後續的數字陣列可能會儲存在不同的位置，即使它包含相同的資料。如果發生這種情況，Memoize 會認為引數不同，即使它們是等效的。在這種情況下，適用的正規化器如下所示
sub normalize { join ' ', $_[0], @{$_[1]} }對於上述範例，這會產生金鑰「13 1 2 3 4 5 6 7」。
正規化器的另一個用途是當函數依賴於引數中以外的資料時。假設您有一個函數，它傳回一個值，該值取決於當天的目前小時數
sub on_duty {
my ($problem_type) = @_;
my $hour = (localtime)[2];
open my $fh, "$DIR/$problem_type" or die...;
my $line;
while ($hour-- > 0)
$line = <$fh>;
}
return $line;
}在 10:23，此函數產生資料檔案的第 10 行；在下午 3:45，它產生第 15 行。預設情況下，Memoize 只會看到 $problem_type 參數。若要修正此問題，請在正規化器中包含目前小時
sub normalize { join ' ', (localtime)[2], @_ }函數的呼叫內容（純量或清單內容）會傳遞至正規化器。這表示如果備忘函數在清單內容中處理其參數的方式與在純量內容中處理的方式不同，您可以讓正規化器函數根據 wantarray 的結果選擇其行為。即使在清單內容中呼叫，正規化器仍應傳回單一字串。
SCALAR_CACHE, LIST_CACHE通常，Memoize 會將函數的傳回值快取至一般的 Perl hash 變數。不過，您可能希望將值快取至磁碟，以便在程式執行期間持續存在，或者您可能希望將一些其他有趣的語意與快取值關聯起來。
Memoize 的內部有一個小複雜性：實際上有兩個快取，一個用於純量值，一個用於清單值。當您的函數在純量內容中呼叫時，其傳回值會快取在一個 hash 中，而當您的函數在清單內容中呼叫時，其值會快取在另一個 hash 中。您可以使用這些選項獨立控制兩個內容的快取行為。
LIST_CACHE 或 SCALAR_CACHE 的參數必須是下列四個字串之一
MEMORY
FAULT
MERGE
HASH否則它必須是對陣列的參考，其第一個元素是這四個字串之一，例如 [HASH, arguments...]。
MEMORYMEMORY 表示函數的傳回值會快取在一般的 Perl hash 變數中。在程式結束後，hash 變數不會持續存在。這是預設值。
HASHHASH 讓您可以指定您提供的特定 hash 將用作快取。您可以在事先繫結此 hash，以賦予它您想要的任何行為。
繫結的 hash 可以具有任何語意。它通常繫結至磁碟資料庫，以便快取值儲存在資料庫中，並在需要時再次從資料庫中擷取，而磁碟檔案通常會在程式結束後持續存在。請參閱 perltie 以取得關於 tie 的更完整詳細資料。
一個典型的範例是
use DB_File;
tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];這會將快取儲存在名稱為 $filename 的 DB_File 資料庫中。快取會在程式結束後持續存在。下次執行程式時，它會發現快取已從程式的上一次執行中填入。或者，您可以建立在背景中執行並填入快取檔案的批次程式來強制填入快取。然後，當您執行實際程式時，備忘函式會很快，因為其所有結果都已預先計算。
使用 HASH 的另一個原因是提供您自己的雜湊變數。然後，您可以檢查或修改雜湊的內容以更精細地控制快取管理。
TIE此選項不再受支援。它仍然有文件記載，只是為了協助偵錯使用它的舊程式。舊程式應轉換為改用 HASH 選項。
memoize ... ['TIE', PACKAGE, ARGS...]只是
require PACKAGE;
{ tie my %cache, PACKAGE, ARGS...;
memoize ... [HASH => \%cache];
}FAULTFAULT 表示您不希望在純量（或清單）內容中呼叫函式，而且如果 Memoize 偵測到此類呼叫，它應中止程式。錯誤訊息之一為
`foo' function called in forbidden list context at line ...
`foo' function called in forbidden scalar context at line ...MERGEMERGE 通常表示備忘函式不會區分清單和純量內容，而且應將這兩個內容的傳回值儲存在一起。LIST_CACHE => MERGE 和 SCALAR_CACHE => MERGE 兩者表示相同的意思。
考慮此函式
sub complicated {
# ... time-consuming calculation of $result
return $result;
}無論 complicated 函式是在清單或純量內容中呼叫，它都會傳回相同的數字 $result。
通常，下列程式碼會導致呼叫 complicated 兩次，即使 complicated 已備忘
$x = complicated(142);
($y) = complicated(142);
$z = complicated(142);第一次呼叫會將結果（例如 37）快取到純量快取中；第二次會將清單 (37) 快取到清單快取中。第三次呼叫不會呼叫實際的 complicated 函式；它會從純量快取取得值 37。
很明顯地，第二次呼叫 complicated 是浪費時間，而且儲存其傳回值是浪費空間。指定 LIST_CACHE => MERGE 會讓 memoize 對純量和清單內容傳回值使用相同的快取，因此第二次呼叫會使用第一次呼叫填入的純量快取。complicated 最後只會被呼叫一次，而且後續呼叫都會從快取傳回 37，不論呼叫內容為何。
考慮此函式
sub iota { return reverse (1..$_[0]) }此函數通常會傳回一個清單。假設您將其記憶並合併快取
memoize 'iota', SCALAR_CACHE => 'MERGE';
@i7 = iota(7);
$i7 = iota(7);這裡的第一個呼叫會快取清單 (1,2,3,4,5,6,7)。第二個呼叫並沒有真正的意義。Memoize 無法猜測 iota 在純量上下文中應該具有的行為，而不會實際在純量上下文中呼叫它。通常 Memoize 會在純量上下文中呼叫 iota 並快取結果，但 SCALAR_CACHE => 'MERGE' 選項表示不要這樣做，而是改用快取清單上下文值。但它無法在純量上下文中傳回一個包含七個元素的清單。在這種情況下，$i7 將接收快取清單值的**第一個元素**，即 7。
MERGE 的另一個用途是當您想要將兩種傳回值儲存在同一個磁碟檔案中時；這讓您不必處理兩個磁碟檔案，而只需處理一個。您可以使用正規化函數來將兩組傳回值分開。例如
local $MLDBM::UseDB = 'DB_File';
tie my %cache => 'MLDBM', $filename, ...;
memoize 'myfunc',
NORMALIZER => 'n',
SCALAR_CACHE => [HASH => \%cache],
LIST_CACHE => 'MERGE',
;
sub n {
my $context = wantarray() ? 'L' : 'S';
# ... now compute the hash key from the arguments ...
$hashkey = "$context:$hashkey";
}此正規化函數會將純量上下文傳回值儲存在磁碟檔案中，其金鑰以 S: 開頭，而清單上下文傳回值則儲存在金鑰以 L: 開頭的檔案中。
unmemoize有一個 unmemoize 函數，如果您願意，可以匯入它。為什麼您會想要這樣做？以下是一個範例：假設您的快取與 DBM 檔案連結，並且您想要確保在有人中斷程式時，快取會寫入磁碟。如果程式正常結束，這將會自動發生，但如果有人按 Control-C 或其他按鍵，則程式將立即終止，而不會同步資料庫。因此，您可以這樣做
$SIG{INT} = sub { unmemoize 'function' };unmemoize 接受先前記憶函數的參考或名稱，並取消它所做的任何事，以提供記憶版本，包括在適當的情況下，讓名稱參照未記憶版本。它傳回函數的未記憶版本參考。
如果您要求它取消記憶一個從未記憶的函數，它會出錯。
flush_cacheflush_cache(function) 將清除快取，捨棄**所有**快取資料。參數可以是函數名稱或函數參考。要更精細地控制何時捨棄或過期資料，請參閱此套件中包含的 Memoize::Expire 文件。
請注意，如果快取是連結雜湊，flush_cache 將嘗試呼叫雜湊上的 CLEAR 方法。如果沒有 CLEAR 方法，這將導致執行時期錯誤。
快取清除的另一種方法是使用 HASH 選項（請見上文），要求 Memoize 使用特定雜湊變數作為其快取。然後，你可以隨時以任何你想要的方式檢查或修改雜湊。你可以使用 %hash = () 清除快取。
記憶化並非萬靈丹
不要記憶化行為取決於程式狀態（而非其自身引數）的函式，例如全域變數、時間或檔案輸入。這些函式在記憶化後將無法產生正確的結果。以下是特別簡單的範例
sub f {
time;
}此函式不接受任何引數，且就 Memoize 而言，它總是傳回相同的結果。當然，Memoize 是錯誤的，而此函式的記憶化版本將呼叫 time 一次以取得目前時間，並且在之後每次呼叫時都將傳回相同時間。
不要記憶化具有副作用的函式。
sub f {
my ($a, $b) = @_;
my $s = $a + $b;
print "$a + $b = $s.\n";
}此函式接受兩個引數，將它們相加並印出其總和。其傳回值為印出的字元數，但你可能不關心這一點。但是 Memoize 不理解這一點。如果你記憶化此函式，你將在第一次要求它印出 2 和 3 的總和時取得預期的結果，但後續呼叫將傳回 1（print 的傳回值），而不會實際印出任何內容。
不要記憶化傳回由呼叫者修改的資料結構的函式。
考慮以下函式：getusers 以某種方式傳回使用者清單，然後 main 捨棄清單中的第一個使用者並印出其餘部分
sub main {
my $userlist = getusers();
shift @$userlist;
foreach $u (@$userlist) {
print "User $u\n";
}
}
sub getusers {
my @users;
# Do something to get a list of users;
\@users; # Return reference to list.
}如果您在此處記憶化 getusers，它將只會準確地執行一次。使用者清單的參考將儲存在記憶化表中。main 會捨棄參考清單中的第一個元素。下次您呼叫 main 時，Memoize 就不會呼叫 getusers；它只會傳回與上次取得相同清單的相同參考。但這次清單的開頭已經被移除；main 會錯誤地從中移除另一個元素。每次呼叫 main 時，清單都會越來越短。
類似地，這
$u1 = getusers();
$u2 = getusers();
pop @$u1;會修改 $u2 和 $u1，因為這兩個變數都是指向同一個陣列的參考。如果 getusers 沒有記憶化，$u1 和 $u2 會指向不同的陣列。
不要記憶化一個非常簡單的函式。
最近有人告訴我，Memoize 模組讓他的程式執行速度變慢，而不是變快。結果發現，他記憶化了以下函式
sub square {
$_[0] * $_[0];
}我指出 Memoize 使用雜湊，而且在雜湊中查詢一個數字一定會比單次乘法花費更長的時間。真的沒有辦法加速 square 函式。
記憶化不是神奇的。
您可以將快取表繫結到任何您想要的繫結雜湊，只要它支援 TIEHASH、FETCH、STORE 和 EXISTS。例如，
tie my %cache => 'GDBM_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];運作良好。對於某些儲存方法，您需要一點膠水。
SDBM_File 沒有提供 EXISTS 方法，因此此套件中包含一個名為 Memoize::SDBM_File 的膠水模組，它確實提供了一個。使用這個模組來取代純粹的 SDBM_File，以將您的快取表儲存在 SDBM_File 資料庫中的磁碟上
tie my %cache => 'Memoize::SDBM_File', $filename, O_RDWR|O_CREAT, 0666;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];NDBM_File 有相同的問題和相同的解決方案。（使用 Memoize::NDBM_File 來取代純粹的 NDBM_File。）
Storable 根本不是一個繫結雜湊類別。您可以使用它將雜湊儲存在磁碟上並再次擷取它，但您無法在雜湊位於磁碟上時修改它。因此，如果您想要將快取表儲存在 Storable 資料庫中，請使用 Memoize::Storable，它會在 Storable 上放置一個類似雜湊的前端。雜湊表實際上會保存在記憶體中，並在您記憶化函式時從您的 Storable 檔案中載入，並在您取消記憶化函式時（或在您的程式結束時）儲存回去
tie my %cache => 'Memoize::Storable', $filename;
memoize 'function', SCALAR_CACHE => [HASH => \%cache];
tie my %cache => 'Memoize::Storable', $filename, 'nstore';
memoize 'function', SCALAR_CACHE => [HASH => \%cache];包含 nstore 選項，以讓 Storable 資料庫以 網路順序 撰寫。（請參閱 Storable 以取得有關此項目的更多詳細資料。）
除非繫結套件提供 CLEAR 方法，否則 flush_cache() 函式會引發執行時期錯誤。
請參閱 Memoize::Expire，它是一個外掛模組，可將過期功能新增到 Memoize。如果您不喜歡 Memoize::Expire 實作的政策類型，可以輕鬆撰寫您自己的外掛模組來實作您想要的任何政策。Memoize 附帶幾個範例。實作 LRU 政策的過期管理員可以在 CPAN 上取得，名稱為 Memoize::ExpireLRU。
測試套件已經好很多了，但仍有進步空間。
goto &f 在執行緒 Perl 中運作的方式有些問題，這可能是因為 @_ 的詞彙範圍。這是 Perl 中的錯誤，在解決之前，備忘功能會看到略有不同的 caller()，而且在執行緒 Perl 中執行速度會比非執行緒 Perl 慢一點。
某些版本的 DB_File 不允許您儲存長度為 0 的金鑰下的資料。這表示如果您有一個已備忘的功能 f，而且快取在 DB_File 資料庫中，則 f() 的值（f 未帶任何引數呼叫）不會備忘。如果這是個大問題，您可以提供一個正規化函式，將 "x" 加到每個金鑰的前面。
在 https://perl.plover.com/MiniMemoize/ 中有一篇文章探討備忘和 Memoize 的內部結構，這篇文章出現在 The Perl Journal 第 13 期。
Mark-Jason Dominus 的著作《高階 Perl》(2005 年，ISBN 1558607013，由 Morgan Kaufmann 出版) 非常詳細地探討備忘(以及許多其他主題)。它可以在線上免費取得。如需更多資訊，請瀏覽 https://hop.perl.plover.com/。
非常感謝 Florian Ragwitz 提供管理和封裝協助，感謝 John Tromp 提供錯誤報告，感謝 Jonathan Roy 提供錯誤報告和建議，感謝 Michael Schwern 提供其他錯誤報告和修補程式，感謝 Mike Cariaso 協助我找出關於過期處理的正確做法，感謝 Joshua Gerth、Joshua Chamas、Jonathan Roy (再次)、Mark D. Anderson 和 Andrew Johnson 提供更多關於過期的建議，感謝 Brent Powers 提供 Memoize::ExpireLRU 模組，感謝 Ariel Scolnicov 提供關於 Fibonacci 函式的令人愉快的訊息，感謝 Dion Almaer 提供關於預設正規化的發人省思的建議，感謝 Walt Mankowski 和 Kurt Starsinic 在執行緒 Perl 下調查問題時提供許多協助，感謝 Alex Dudkevich 報告原型函式中的錯誤並檢查我的修補程式，感謝 Tony Bass 提供許多有用的建議，感謝 Jonathan Roy (再次) 找到 unmemoize() 的用途，感謝 Philippe Verdret 對於 Hook::PrePostCall 的深入探討，感謝 Nat Torkington 提供我忽略的建議，感謝 Chris Nandor 提供可攜性的建議，感謝 Randal Schwartz 建議 flush_cache 函式，以及感謝 Jenda Krynicky 成為世界的一盞明燈。
特別感謝 5.8.0 的 pumpking Jarkko Hietaniemi，感謝他在整合過程中納入這個模組，以及他耐心且有用的指導。
Mark Jason Dominus
此軟體的版權為 (c) 2012 Mark Jason Dominus 所有。
這是自由軟體；您可以在與 Perl 5 程式語言系統相同的條款下重新散布或修改它。