轉(zhuǎn)的這篇文章雖然是講動(dòng)態(tài)代理的
但是其中涉及到了Decorator模式 也是一個(gè)學(xué)習(xí)的亮點(diǎn)
-----------------------------------------------------------------------------------------------------
記憶是衍生自Lisp,Python,和Perl等過程性語言的一種設(shè)計(jì)模式，它可以對(duì)前次的計(jì)算結(jié)果進(jìn)行記憶。 一個(gè)實(shí)現(xiàn)了記憶功能的函數(shù), 帶有顯式的cache, 所以, 已經(jīng)計(jì)算過的結(jié)果就能直接從cache中獲得, 而不用每次都進(jìn)行計(jì)算.
記憶能顯著的提升大計(jì)算量代碼的效率. 而且是一種可重用的方案.
本文闡述了在Java中使用這一模式的方法,并提供了一個(gè)可以提供上述功能的"記憶類":
Foo foo = (Foo) Memoizer.memoize(new FooImpl());
這里,Foo是一個(gè)接口,它含有的方法是需要記憶的.FooImpl是Foo的一個(gè)實(shí)現(xiàn).foo是Foo的一個(gè)引用.方法與FooImpl基本相同,區(qū)別在于Foo返回的值,會(huì)被緩存起來.單個(gè)記憶類的優(yōu)點(diǎn)在于為任何類添加記憶功能是很簡(jiǎn)單的:定義一個(gè)包含需要記憶的方法的接口,然后調(diào)用memoize來實(shí)現(xiàn)一個(gè)實(shí)例.
為了理解記憶類是怎么實(shí)現(xiàn)的,我們將分幾步來解釋.首先,我解釋一下為何緩存能夠在需要它的類中實(shí)現(xiàn).然后,我測(cè)試一下如何為一個(gè)特定的類添加緩存包裝器.最后,我解釋一下如何才能使得一個(gè)緩存包裝器能夠通用于任意的類.
為大計(jì)算量的程序添加緩存
作為一個(gè)大計(jì)算量程序的例子,我們考慮PiBinaryDigitsCalculator這個(gè)例子-計(jì)算二進(jìn)制數(shù)據(jù)pi.僅有的public方法calculateBinaryDigit帶有一個(gè)參數(shù):整數(shù)n,代表需要精確到的位數(shù).例如,1000000,將會(huì)返回小數(shù)點(diǎn)后的一百萬位,通過byte值返回-每位為0或者1.(算法可以參考: http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.pdf)
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 ...
}
}
最簡(jiǎn)單直接的方法來緩存返回值可以通過修改這個(gè)類來實(shí)現(xiàn):添加一個(gè)Map來保存之前計(jì)算得到的值,如下:
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方法首先會(huì)檢查HashMap里面是否緩存了這個(gè)關(guān)鍵字-參數(shù)n,如果找到了,就直接返回這個(gè)值.否則,就會(huì)進(jìn)行這個(gè)冗長(zhǎng)的計(jì)算,并將結(jié)果保存到緩存里面.在添加進(jìn)HashMap的時(shí)候,在原始類型和對(duì)象之間還要進(jìn)行小小的轉(zhuǎn)換.
盡管這個(gè)方法是可行的,但是有幾個(gè)缺點(diǎn).首先,進(jìn)行緩存的代碼和正常的算法代碼不是顯著分開的.一個(gè)類,不僅負(fù)責(zé)進(jìn)行計(jì)算,也要負(fù)責(zé)進(jìn)行維護(hù)緩存數(shù)據(jù).這樣,要進(jìn)行一些測(cè)試就會(huì)顯得很困難.比如,不能寫一個(gè)測(cè)試程序來測(cè)試這個(gè)算法持續(xù)地返回相同的值,因?yàn)?從第二次開始,結(jié)果都是直接從cache中獲得了.
其次,當(dāng)緩存代碼不再需要,移除它會(huì)變得困難,因?yàn)樗退惴▔K地代碼是緊密結(jié)合在一起的.所以,要想知道緩存是否帶來了很高的效率提升也是很困難的,因?yàn)椴荒軐懸粋€(gè)測(cè)試程序是和緩存數(shù)據(jù)分開的.當(dāng)你改進(jìn)了你的算法,緩存有可能失效-但是這個(gè)時(shí)候你并不知道.
第三,緩存代碼不能被重用.盡管代碼遵從了一個(gè)普通的模式,但是都是在一個(gè)類- PiBinaryDigitsCalculator里面.
前面兩個(gè)問題都可以通過構(gòu)造一個(gè)緩存包裝器來解決.
緩存包裝器
通過使用Decorator模式,要分開計(jì)算代碼和緩存代碼是很容易的.首先,定義一個(gè)接口,里面定義基本的方法.
public interface BinaryDigitsCalculator {
public byte calculateBinaryDigit(final int n);
}
然后定義兩個(gè)實(shí)現(xiàn),分別負(fù)責(zé)兩個(gè)任務(wù):
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();
}
}
}
這是很之前的實(shí)現(xiàn)PiBinaryDigitsCalculator的一種簡(jiǎn)單的refactored版本. CachingBinaryDigitsCalculator包裝了BinaryDigitsCalculator句柄,并增加了緩存,供calculateBinaryDigit的方法調(diào)用. 這種方法提高了代碼的可讀性與可維護(hù)性. 用戶不能直接使用BinaryDigitsCalculator接口來實(shí)現(xiàn)算法,所以,如果需要關(guān)閉緩存塊,將是很容易實(shí)現(xiàn)的.
還有,合適的測(cè)試程序很容易寫出來.比如,我們寫一個(gè)假的BinaryDigitsCalculator實(shí)現(xiàn),每次calculateBinaryDigit被調(diào)用,賦予相同的參數(shù),返回不同的值. 這樣,我們就能測(cè)試緩存是否工作了,因?yàn)槿绻看味挤祷叵嗤闹?則證明緩存是正常工作了. 這種測(cè)試在之前那種簡(jiǎn)單的實(shí)現(xiàn)是不可能的.
這是很之前的實(shí)現(xiàn)PiBinaryDigitsCalculator的一種簡(jiǎn)單的refactored版本. CachingBinaryDigitsCalculator包裝了BinaryDigitsCalculator句柄,并增加了緩存,供calculateBinaryDigit的方法調(diào)用. 這種方法提高了代碼的可讀性與可維護(hù)性. 用戶不能直接使用BinaryDigitsCalculator接口來實(shí)現(xiàn)算法,所以,如果需要關(guān)閉緩存塊,將是很容易實(shí)現(xiàn)的.
還有,合適的測(cè)試程序很容易寫出來.比如,我們寫一個(gè)假的BinaryDigitsCalculator實(shí)現(xiàn),每次calculateBinaryDigit被調(diào)用,賦予相同的參數(shù),返回不同的值. 這樣,我們就能測(cè)試緩存是否工作了,因?yàn)槿绻看味挤祷叵嗤闹?則證明緩存是正常工作了. 這種測(cè)試在之前那種簡(jiǎn)單的實(shí)現(xiàn)是不可能的。
通過動(dòng)態(tài)代理類來創(chuàng)建一個(gè)通用的緩存包裝器\r
上面第二種方法僅有的缺點(diǎn)就是緩存包裝器不能重用,每次我們希望添加一個(gè)緩存給某個(gè)類,我們就要寫一個(gè)特殊的緩存包裝器給目標(biāo)接口.這是一個(gè)很慢,容易出錯(cuò)的過程.
Jdk1.3開始支持動(dòng)態(tài)代理類: 特別的類能夠在運(yùn)行期決定實(shí)現(xiàn)哪個(gè)接口-通常的模式都是,在運(yùn)行期即決定實(shí)現(xiàn)哪個(gè)接口.通過這個(gè),我們有可能實(shí)現(xiàn)一個(gè)通用的緩存包裝器,我們稱它為Memoizer,在運(yùn)行期決定實(shí)現(xiàn)哪個(gè)接口.這樣, CachingBinaryDigitsCalculator就是不再需要的.它是這樣被調(diào)用的:
BinaryDigitsCalculator calculator =
new CachingBinaryDigitsCalculator(
new PiBinaryDigitsCalculator()
);
可以通過Memoizer來重寫如下:
BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator()
);
Memoizer的代碼如下:
package demo.proxy;
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 Memorizer implements InvocationHandler 
{
public static Object memorize(Object object) {
return Proxy.newProxyInstance(object.getClass().getClassLoader(),
object.getClass().getInterfaces(), new Memorizer(object));
}
private Object object;
private Map caches = new HashMap();
private Memorizer(Object object) {
this.object = object;
}
public Object invoke(Object proxy, Method method, Object[] args)
throws Throwable {
// Don't cache void methods
if (method.getReturnType().equals(Void.TYPE)) {
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;
}
}
當(dāng)調(diào)用靜態(tài)方法memoize的時(shí)候,將會(huì)創(chuàng)建一個(gè)新的代理實(shí)例-也就是一個(gè)java.lang.reflect.proxy的實(shí)例.實(shí)現(xiàn)了一個(gè)接口集.這個(gè)接口集由object.getClass().getInterfaces()來決定.每個(gè)代理實(shí)例包含一個(gè)java.lang.reflect.InvocationHandler實(shí)例來處理這個(gè)代理實(shí)例調(diào)用的相關(guān)方法.在我們的例子里,Memoizer就是一個(gè)InvocationHandler實(shí)例.
當(dāng)一個(gè)方法在代理實(shí)例里被調(diào)用,比如, calculateBinaryDigit,那么, Memoizer實(shí)例里的invoke方法就會(huì)被調(diào)用,相關(guān)信息會(huì)傳給invoke方法,以決定proxy實(shí)例調(diào)用了哪個(gè)方法,包含參數(shù)信息.在我們的例子里,傳入Memoizer的java.lang.Method參數(shù)是calculateBinaryDigit,而參數(shù)信息則是pi需要精確的位數(shù)-整數(shù)n.在這個(gè)基礎(chǔ)上,Memoizer能夠進(jìn)一步進(jìn)行緩存操作的.
在例子里(caches是一個(gè)Hashmap,cache是一個(gè)map)里用到的Key,主要是傳入的方法信息:Method對(duì)象和參數(shù)對(duì)象. 為了實(shí)現(xiàn)的簡(jiǎn)單與通用性,Memoizer有一個(gè)關(guān)于cache的HashMap caches,每個(gè)method是一個(gè)key,對(duì)應(yīng)的value為一個(gè)cache.然后把參數(shù)信息轉(zhuǎn)化成一個(gè)List對(duì)象,作為cache的Key.使用List是很方便的,同時(shí)也可以保證equals()方法,所以能夠保證當(dāng)且僅當(dāng)參數(shù)信息完全相同的時(shí)候這個(gè)List才相等.
一旦一個(gè)cache的Key被創(chuàng)建,那么,計(jì)算之前都會(huì)先查找這個(gè)cache,如果找到,則返回cache里的值.否則,如果帶有這些參數(shù)的這個(gè)方法沒有被調(diào)用過,那么,則會(huì)通過invoke來調(diào)用這個(gè)method.在我們的例子里, 實(shí)例PiBinaryDigitsCalculator 里的calculateBinaryDigit方法將會(huì)通過invoke被調(diào)用.而且計(jì)算結(jié)果將會(huì)被存在cache里.
何時(shí)使用Memoizer
作為一條通用的規(guī)則,Memoizer能夠在任何需要傳統(tǒng)的cache的時(shí)候使用-比如上面提到的例子. 特別地,接口里每個(gè)需要使用記憶功能的method需要滿足下面幾條條件:
1. 這個(gè)method的返回值最好不要每次調(diào)用都會(huì)改變\r
2. 這個(gè)method不要有副效應(yīng)
3. 這個(gè)method的參數(shù)是確定的,非mutable的.
顯然,如果每次調(diào)用這個(gè)method返回值都不同,那么cache就毫無用處了.同樣也是很重要的一點(diǎn)是,因?yàn)橛懈毙?yīng)的method不會(huì)被重復(fù),所以這個(gè)method不能有副效應(yīng)(method自動(dòng)更新某些狀態(tài)).當(dāng)然,void方法除外.
同樣,memorize一個(gè)帶有未定(mutable)參數(shù)的method是很危險(xiǎn)的,因?yàn)?要把這些參數(shù)儲(chǔ)存到hashmap里會(huì)是很危險(xiǎn)的一件事.根據(jù)Map的定義,當(dāng)這個(gè)Map里的key發(fā)生改變,Map是不知道的.所以,當(dāng)你執(zhí)行了一次這個(gè)method之后,相關(guān)信息添加進(jìn)了Map,然后參數(shù)發(fā)生變異(mutate),第二次調(diào)用的時(shí)候,就會(huì)得到錯(cuò)誤的結(jié)果.
性能
使用cache的主要目的就是為了提升你的程序的速度.然而,reflection確是眾所周知的低效(在jdk1.4里有所改進(jìn),通過reflection調(diào)用方法是普通調(diào)用速度的1/2,這個(gè)比jdk1.3要快40倍).Memoizer主要依靠reflection來調(diào)用方法,所以,它看上去并不是一個(gè)好的途徑.但是,如果使用cache能給程序速度帶來的提升遠(yuǎn)高于reflection對(duì)速度的影響,那么,使用Memoizer是值得考慮的.
在我們對(duì)PiBinaryDigitsCalculator的測(cè)試中,測(cè)試環(huán)境為jdk1.4,當(dāng)n小于10的時(shí)候,使不使用cache速度是相當(dāng)?shù)?但是,當(dāng)n增大的時(shí)候,使用cache的優(yōu)勢(shì)就開始顯示出來.所以,經(jīng)常使用PiBinaryDigitsCalculator的用戶,可以考慮使用cache.
不幸的是,唯一測(cè)試你的程序是否需要cache的途徑是比較你的程序在兩種情況下的運(yùn)行效率.盡管如此,因?yàn)闉橐粋€(gè)程序構(gòu)造一個(gè)cache包裝器是很容易的一件事,移除它也是很容易的,下面的建議可以作為一個(gè)參考的步驟:
1. 選擇需要記憶操作的類\r
2. 運(yùn)行它\r
3. 如果效率是滿意的,go to 6
4. 添加memoizer,使用cache
5. 如果效率沒有顯著提升,移初memoizer
6. 如果需要,重試.
理論上,你需要分析為一個(gè)類添加記憶功能對(duì)整個(gè)系統(tǒng)的影響.只有你自己清楚是否值得添加.有些方法,即使是計(jì)算量很大的,但是在這個(gè)系統(tǒng)里很少被調(diào)用,所以,沒必要為它添加記憶功能.為了保證這個(gè),我開發(fā)了一個(gè)更有特點(diǎn)的Memoizer,實(shí)現(xiàn)了一個(gè)叫做CacheStatistics的接口,你能從它得到cache的數(shù)量以及無效的cache.你可以使用它作為判斷的一個(gè)尺度.
擴(kuò)展Memoizer
修改Memoizer類來支持不同的cache策略是很簡(jiǎn)單的.一個(gè)比較普通的類型就是Least-Recently-Used(LRU)cahce,擁有固定數(shù)量的入口.這個(gè)cache確保入口不大于它的最大數(shù)目,如果超過,就摒棄最舊的緩存數(shù)據(jù).也就是,能夠從cache里得到的是新的數(shù)據(jù).一個(gè)類可以使用LRU cache來防止一個(gè)程序長(zhǎng)期保持一個(gè)狀態(tài).你可以僅僅傳遞一個(gè)參數(shù)給CacheFactory里的memoize方法來選擇你需要的cache類型.下面的例子,LRU cache最多有1000個(gè)入口:
BinaryDigitsCalculator calculator =
(BinaryDigitsCalculator) Memoizer.memoize(
new PiBinaryDigitsCalculator(),
new LruCacheFactory(1000)
);
即使是這么簡(jiǎn)單,Memoizer也應(yīng)該是java程序員一個(gè)有用的工具.