記憶是衍生自Lisp,Python,和Perl等過程性語言的一種設計模式，它可以對前次的計算結果進行記憶。 一個實現了記憶功能的函數, 帶有顯式的cache, 所以, 已經計算過的結果就能直接從cache中獲得, 而不用每次都進行計算.

記憶能顯著的提升大計算量代碼的效率. 而且是一種可重用的方案.

本文闡述了在Java中使用這一模式的方法,并提供了一個可以提供上述功能的"記憶類":

Foo foo = (Foo) Memoizer.memoize(new FooImpl());

這里,Foo是一個接口,它含有的方法是需要記憶的.FooImpl是Foo的一個實現.foo是Foo的一個引用.方法與FooImpl基本相同,區別在于Foo返回的值,會被緩存起來.單個記憶類的優點在于為任何類添加記憶功能是很簡單的:定義一個包含需要記憶的方法的接口,然后調用memoize來實現一個實例.

為了理解記憶類是怎么實現的,我們將分幾步來解釋.首先,我解釋一下為何緩存能夠在需要它的類中實現.然后,我測試一下如何為一個特定的類添加緩存包裝器.最后,我解釋一下如何才能使得一個緩存包裝器能夠通用于任意的類.

為大計算量的程序添加緩存

作為一個大計算量程序的例子,我們考慮PiBinaryDigitsCalculator這個例子-計算二進制數據pi.僅有的public方法calculateBinaryDigit帶有一個參數:整數n,代表需要精確到的位數.例如,1000000,將會返回小數點后的一百萬位,通過byte值返回-每位為0或者1.

public class PiBinaryDigitsCalculator { /** * Returns the coefficient of 2^n in the binary * expansion of pi. * @param n the binary digit of pi to calculate. * @throws ValidityCheckFailedException if the validity * check fails, this means the implementation is buggy * or n is too large for sufficient precision to be * retained. */ public byte calculateBinaryDigit(final int n) { return runBBPAlgorithm(n); } private byte runBBPAlgorithm(final int n) { // Lengthy routine goes here ... } }

最簡單直接的方法來緩存返回值可以通過修改這個類來實現:添加一個Map來保存之前計算得到的值,如下:

import java.util.HashMap; public class PiBinaryDigitsCalculator { private HashMap cache = new HashMap(); public synchronized byte calculateBinaryDigit( final int n) { final Integer N = new Integer(n); Byte B = (Byte) cache.get(N); if (B == null) { byte b = runBBPAlgorithm(n); cache.put(N, new Byte(b)); return b; } else { return B.bytevalue(); } } private byte runBBPAlgorithm(final int n) { // Lengthy routine goes here ... } }

calculateBinaryDigit方法首先會檢查HashMap里面是否緩存了這個關鍵字-參數n,如果找到了,就直接返回這個值.否則,就會進行這個冗長的計算,并將結果保存到緩存里面.在添加進HashMap的時候,在原始類型和對象之間還要進行小小的轉換.

盡管這個方法是可行的,但是有幾個缺點.首先,進行緩存的代碼和正常的算法代碼不是顯著分開的.一個類,不僅負責進行計算,也要負責進行維護緩存數據.這樣,要進行一些測試就會顯得很困難.比如,不能寫一個測試程序來測試這個算法持續地返回相同的值,因為,從第二次開始,結果都是直接從cache中獲得了.

其次,當緩存代碼不再需要,移除它會變得困難,因為它和算法塊地代碼是緊密結合在一起的.所以,要想知道緩存是否帶來了很高的效率提升也是很困難的,因為不能寫一個測試程序是和緩存數據分開的.當你改進了你的算法,緩存有可能失效-但是這個時候你并不知道.

第三,緩存代碼不能被重用.盡管代碼遵從了一個普通的模式,但是都是在一個類- PiBinaryDigitsCalculator里面.

前面兩個問題都可以通過構造一個緩存包裝器來解決.