用Java动态署理类实现影象成果

副标题#e#

影象是衍生自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 ...
}
}

#p#副标题#e#

最简朴直接的要领来缓存返回值可以通过修改这个类来实现:添加一个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);
}

#p#副标题#e#

然后界说两个实现,别离认真两个任务:

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();
}
}
}
 

#p#分页标题#e#

这是很之前的实现PiBinaryDigitsCalculator的一种简朴的refactored版本. CachingBinaryDigitsCalculator包装了BinaryDigitsCalculator句柄,并增加了缓存,供calculateBinaryDigit的要领挪用. 这种要领提高了代码的可读性与可维护性. 用户不能直接利用BinaryDigitsCalculator接口来实现算法,所以,假如需要封锁缓存块,将是很容易实现的.

尚有,符合的测试措施很容易写出来.好比,我们写一个假的BinaryDigitsCalculator实现,每次calculateBinaryDigit被挪用,赋予沟通的参数,返回差异的值. 这样,我们就能测试缓存是否事情了,因为假如每次都返回沟通的值,则证明缓存是正常事情了. 这种测试在之前那种简朴的实现是不行能的。

通过动态署理类来建设一个通用的缓存包装器

上面第二种要领仅有的缺点就是缓存包装器不能重用,每次我们但愿添加一个缓存给某个类,我们就要写一个非凡的缓存包装器给方针接口.这是一个很慢,容易堕落的进程.

Jdk1.3开始支持动态署理类: 出格的类可以或许在运行期抉择实现哪个接口-凡是的模式都是,在运行期即抉择实现哪个接口.通过这个,我们有大概实现一个通用的缓存包装器,我们称它为Memoizer,在运行期抉择实现哪个接口.这样, CachingBinaryDigitsCalculator就是不再需要的.它是这样被挪用的:

BinaryDigitsCalculator calculator =
new CachingBinaryDigitsCalculator(
new PiBinaryDigitsCalculator()
);

#p#副标题#e#

可以通过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;
}
}

#p#副标题#e#

当挪用静态要领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才相等.

#p#分页标题#e#

一旦一个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),第二次挪用的时候,就会获得错误的功效.

#p#副标题#e#

机能

利用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措施员一个有用的东西.