記憶是衍生自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裡面.
前面兩個問題都可以通過構造一個緩存包裝器來解決.
緩存包裝器
通過使用Decorator模式,要分開計算代碼和緩存代碼是很容易的.首先,定義一個接口,裡面定義基本的方法.
public interface BinaryDigitsCalculator {
public byte calculateBinaryDigit(final int n);
}
然後定義兩個實現,分別負責兩個任務:
public class PiBinaryDigitsCalculator
implements BinaryDigitsCalculator {
public byte calculateBinaryDigit(final int n) {
return runBBPAlgorithm(n);
}
private byte runBBPAlgorithm(final int n) {
// Lengthy routine goes here ...
}
}
import java.util.HashMap;
public class CachingBinaryDigitsCalculator implements
BinaryDigitsCalculator {
private BinaryDigitsCalculator binaryDigitsCalculator;
private HashMap cache = new HashMap();
public CachingBinaryDigitsCalculator(
BinaryDigitsCalculator calculator) {
this.binaryDigitsCalculator = calculator;
}
public synchronized byte calculateBinaryDigit(int n) {
final Integer N = new Integer(n);
Byte B = (Byte) cache.get(N);
if (B == null) {
byte b =
binaryDigitsCalculator.calculateBinaryDigit(n);
cache.put(N, new Byte(b));
return b;
} else {
return B.bytevalue();
}
}
}
這是很之前的實現PiBinaryDigitsCalculator的一種簡單的refactored版本. CachingBinaryDigitsCalculator包裝了BinaryDigitsCalculator句柄,並增加了緩存,供calculateBinaryDigit的方法調用. 這種方法提高了代碼的可讀性與可維護性. 用戶不能直接使用BinaryDigitsCalculator接口來實現算法,所以,如果需要關閉緩存塊,將是很容易實現的.
還有,合適的測試程序很容易寫出來.比如,我們寫一個假的BinaryDigitsCalculator實現,每次calculateBinaryDigit被調用,賦予相同的參數,返回不同的值. 這樣,我們就能測試緩存是否工作了,因為如果每次都返回相同的值,則證明緩存是正常工作了. 這種測試在之前那種簡單的實現是不可能的。
通過動態代理類來創建一個通用的緩存包裝器
上面第二種方法僅有的缺點就是緩存包裝器不能重用,每次我們希望添加一個緩存給某個類,我們就要寫一個特殊的緩存包裝器給目標接口.這是一個很慢,容易出錯的過程.
Jdk1.3開始支持動態代理類: 特別的類能夠在運行期決定實現哪個接口-通常的模式都是,在運行期即決定實現哪個接口.通過這個,我們有可能實現一個通用的緩存包裝器,我們稱它為Memoizer,在運行期決定實現哪個接口.這樣, CachingBinaryDigitsCalculator就是不再需要的.它是這樣被調用的:
BinaryDigitsCalculator calculator =
new CachingBinaryDigitsCalculator(
new PiBinaryDigitsCalculator()
);
可以通過Memoizer來重寫如下:
BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator()
);
Memoizer的代碼如下:
import java.lang.reflect.InvocationHandler;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.lang.reflect.Proxy;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Memoizer implements InvocationHandler {
public static Object memoize(Object object) {
return Proxy.newProxyInstance(
object.getClass().getClassLoader(),
object.getClass().getInterfaces(),
new Memoizer(object)
);
}
private Object object;
private Map caches = new HashMap();
private Memoizer(Object object) {
this.object = object;
}
public Object invoke(Object proxy, Method method,
Object[] args) throws Throwable {
if (method.getReturnType().equals(Void.TYPE)) {
// Don't cache void methods
return invoke(method, args);
} else {
Map cache = getCache(method);
List key = Arrays.asList(args);
Object value = cache.get(key);
if (value == null && !cache.containsKey(key)) {
value = invoke(method, args);
cache.put(key, value);
}
return value;
}
}
private Object invoke(Method method, Object[] args)
throws Throwable {
try {
return method.invoke(object, args);
} catch (InvocationTargetException e) {
throw e.getTargetException();
}
}
private synchronized Map getCache(Method m) {
Map cache = (Map) caches.get(m);
if (cache == null) {
cache = Collections.synchronizedMap(
new HashMap()
);
caches.put(m, cache);
}
return cache;
}
}
當調用靜態方法memoize的時候,將會創建一個新的代理實例-也就是一個java.lang.reflect.proxy的實例.實現了一個接口集.這個接口集由object.getClass().getInterfaces()來決定.每個代理實例包含一個java.lang.reflect.InvocationHandler實例來處理這個代理實例調用的相關方法.在我們的例子裡,Memoizer就是一個InvocationHandler實例.
當一個方法在代理實例裡被調用,比如, calculateBinaryDigit,那麼, Memoizer實例裡的invoke方法就會被調用,相關信息會傳給invoke方法,以決定proxy實例調用了哪個方法,包含參數信息.在我們的例子裡,傳入Memoizer的java.lang.Method參數是calculateBinaryDigit,而參數信息則是pi需要精確的位數-整數n.在這個基礎上,Memoizer能夠進一步進行緩存操作的.
在例子裡(caches是一個Hashmap,cache是一個map)裡用到的Key,主要是傳入的方法信息:Method對象和參數對象. 為了實現的簡單與通用性,Memoizer有一個關於cache的HashMap caches,每個method是一個key,對應的value為一個cache.然後把參數信息轉化成一個List對象,作為cache的Key.使用List是很方便的,同時也可以保證equals()方法,所以能夠保證當且僅當參數信息完全相同的時候這個List才相等.
一旦一個cache的Key被創建,那麼,計算之前都會先查找這個cache,如果找到,則返回cache裡的值.否則,如果帶有這些參數的這個方法沒有被調用過,那麼,則會通過invoke來調用這個method.在我們的例子裡, 實例PiBinaryDigitsCalculator 裡的calculateBinaryDigit方法將會通過invoke被調用.而且計算結果將會被存在cache裡.
何時使用Memoizer
作為一條通用的規則,Memoizer能夠在任何需要傳統的cache的時候使用-比如上面提到的例子. 特別地,接口裡每個需要使用記憶功能的method需要滿足下面幾條條件:
1. 這個method的返回值最好不要每次調用都會改變
2. 這個method不要有副效應
3. 這個method的參數是確定的,非mutable的.
顯然,如果每次調用這個method返回值都不同,那麼cache就毫無用處了.同樣也是很重要的一點是,因為有副效應的method不會被重復,所以這個method不能有副效應(method自動更新某些狀態).當然,void方法除外.
同樣,memorize一個帶有未定(mutable)參數的method是很危險的,因為,要把這些參數儲存到hashmap裡會是很危險的一件事.根據Map的定義,當這個Map裡的key發生改變,Map是不知道的.所以,當你執行了一次這個method之後,相關信息添加進了Map,然後參數發生變異(mutate),第二次調用的時候,就會得到錯誤的結果.
性能
使用cache的主要目的就是為了提升你的程序的速度.然而,reflection確是眾所周知的低效(在jdk1.4裡有所改進,通過reflection調用方法是普通調用速度的1/2,這個比jdk1.3要快40倍).Memoizer主要依靠reflection來調用方法,所以,它看上去並不是一個好的途徑.但是,如果使用cache能給程序速度帶來的提升遠高於reflection對速度的影響,那麼,使用Memoizer是值得考慮的.
在我們對PiBinaryDigitsCalculator的測試中,測試環境為jdk1.4,當n小於10的時候,使不使用cache速度是相當的.但是,當n增大的時候,使用cache的優勢就開始顯示出來.所以,經常使用PiBinaryDigitsCalculator的用戶,可以考慮使用cache.
不幸的是,唯一測試你的程序是否需要cache的途徑是比較你的程序在兩種情況下的運行效率.盡管如此,因為為一個程序構造一個cache包裝器是很容易的一件事,移除它也是很容易的,下面的建議可以作為一個參考的步驟:
1. 選擇需要記憶操作的類
2. 運行它
3. 如果效率是滿意的,go to 6
4. 添加memoizer,使用cache
5. 如果效率沒有顯著提升,移初memoizer
6. 如果需要,重試.
理論上,你需要分析為一個類添加記憶功能對整個系統的影響.只有你自己清楚是否值得添加.有些方法,即使是計算量很大的,但是在這個系統裡很少被調用,所以,沒必要為它添加記憶功能.為了保證這個,我開發了一個更有特點的Memoizer,實現了一個叫做CacheStatistics的接口,你能從它得到cache的數量以及無效的cache.你可以使用它作為判斷的一個尺度.
擴展Memoizer
修改Memoizer類來支持不同的cache策略是很簡單的.一個比較普通的類型就是Least-Recently-Used(LRU)cahce,擁有固定數量的入口.這個cache確保入口不大於它的最大數目,如果超過,就摒棄最舊的緩存數據.也就是,能夠從cache裡得到的是新的數據.一個類可以使用LRU cache來防止一個程序長期保持一個狀態.你可以僅僅傳遞一個參數給CacheFactory裡的memoize方法來選擇你需要的cache類型.下面的例子,LRU cache最多有1000個入口:
BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator(),
new LruCacheFactory(1000)
);
即使是這麼簡單,Memoizer也應該是java程序員一個有用的工具.
