记忆是衍生自Lisp,Python,和Perl等过程性语言的一种设计模式,它可以对前次的计算结果进行记忆。一个实现了记忆功能的函数,带有显式的cache,所以,已经计算过的结果就能直接从cache中获得,而不用每次都进行计算.
记忆能显著的提升大计算量代码的效率.而且是一种可重用的方案.
本文阐述了在Java中使用这一模式的方法,并提供了一个可以提供上述功能的"记忆类":
Foofoo=(Foo)Memoizer.memoize(newFooImpl());
这里,Foo是一个接口,它含有的方法是需要记忆的.FooImpl是Foo的一个实现.foo是Foo的一个引用.方法与FooImpl基本相同,区别在于Foo返回的值,会被缓存起来.单个记忆类的优点在于为任何类添加记忆功能是很简单的:定义一个包含需要记忆的方法的接口,然后调用memoize来实现一个实例.
为了理解记忆类是怎么实现的,我们将分几步来解释.首先,我解释一下为何缓存能够在需要它的类中实现.然后,我测试一下如何为一个特定的类添加缓存包装器.最后,我解释一下如何才能使得一个缓存包装器能够通用于任意的类.
为大计算量的程序添加缓存作为一个大计算量程序的例子,我们考虑PiBinaryDigitsCalculator这个例子-计算二进制数据pi.仅有的public方法calculateBinaryDigit带有一个参数:整数n,代表需要精确到的位数.例如,1000000,将会返回小数点后的一百万位,通过byte值返回-每位为0或者1.(算法可以参考:
http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.pdf)
publicclassPiBinaryDigitsCalculator{ /** *Returnsthecoefficientof2^ninthebinary *expansionofpi. *@paramnthebinarydigitofpitocalculate. *@throwsValidityCheckFailedExceptionifthevalidity *checkfails,thismeanstheimplementationisbuggy *ornistoolargeforsufficientprecisiontobe *retained. */ publicbytecalculateBinaryDigit(finalintn){ returnrunBBPAlgorithm(n); }
privatebyterunBBPAlgorithm(finalintn){ //Lengthyroutinegoeshere... }
} |
最简单直接的方法来缓存返回值可以通过修改这个类来实现:添加一个Map来保存之前计算得到的值,如下:
importjava.util.HashMap;
publicclassPiBinaryDigitsCalculator{
privateHashMapcache=newHashMap();
publicsynchronizedbytecalculateBinaryDigit( finalintn){
finalIntegerN=newInteger(n); ByteB=(Byte)cache.get(N); if(B==null){ byteb=runBBPAlgorithm(n); cache.put(N,newByte(b)); returnb; }else{ returnB.bytevalue(); } }
privatebyterunBBPAlgorithm(finalintn){ //Lengthyroutinegoeshere... } } |
calculateBinaryDigit方法首先会检查HashMap里面是否缓存了这个关键字-参数n,如果找到了,就直接返回这个值.否则,就会进行这个冗长的计算,并将结果保存到缓存里面.在添加进HashMap的时候,在原始类型和对象之间还要进行小小的转换.
尽管这个方法是可行的,但是有几个缺点.首先,进行缓存的代码和正常的算法代码不是显著分开的.一个类,不仅负责进行计算,也要负责进行维护缓存数据.这样,要进行一些测试就会显得很困难.比如,不能写一个测试程序来测试这个算法持续地返回相同的值,因为,从第二次开始,结果都是直接从cache中获得了.
其次,当缓存代码不再需要,移除它会变得困难,因为它和算法块地代码是紧密结合在一起的.所以,要想知道缓存是否带来了很高的效率提升也是很困难的,因为不能写一个测试程序是和缓存数据分开的.当你改进了你的算法,缓存有可能失效-但是这个时候你并不知道.
第三,缓存代码不能被重用.尽管代码遵从了一个普通的模式,但是都是在一个类-PiBinaryDigitsCalculator里面.
前面两个问题都可以通过构造一个缓存包装器来解决.
缓存包装器通过使用Decorator模式,要分开计算代码和缓存代码是很容易的.首先,定义一个接口,里面定义基本的方法.
publicinterfaceBinaryDigitsCalculator{
publicbytecalculateBinaryDigit(finalintn); } |
然后定义两个实现,分别负责两个任务:
publicclassPiBinaryDigitsCalculator implementsBinaryDigitsCalculator{
publicbytecalculateBinaryDigit(finalintn){ returnrunBBPAlgorithm(n); }
privatebyterunBBPAlgorithm(finalintn){ //Lengthyroutinegoeshere... }
}
importjava.util.HashMap;
publicclassCachingBinaryDigitsCalculatorimplements BinaryDigitsCalculator{
privateBinaryDigitsCalculatorbinaryDigitsCalculator; privateHashMapcache=newHashMap();
publicCachingBinaryDigitsCalculator( BinaryDigitsCalculatorcalculator){ this.binaryDigitsCalculator=calculator; }
publicsynchronizedbytecalculateBinaryDigit(intn){ finalIntegerN=newInteger(n); ByteB=(Byte)cache.get(N); if(B==null){ byteb= binaryDigitsCalculator.calculateBinaryDigit(n); cache.put(N,newByte(b)); returnb; }else{ returnB.bytevalue(); } } } |
这是很之前的实现PiBinaryDigitsCalculator的一种简单的refactored版本.CachingBinaryDigitsCalculator包装了BinaryDigitsCalculator句柄,并增加了缓存,供calculateBinaryDigit的方法调用.这种方法提高了代码的可读性与可维护性.用户不能直接使用BinaryDigitsCalculator接口来实现算法,所以,如果需要关闭缓存块,将是很容易实现的.
还有,合适的测试程序很容易写出来.比如,我们写一个假的BinaryDigitsCalculator实现,每次calculateBinaryDigit被调用,赋予相同的参数,返回不同的值.这样,我们就能测试缓存是否工作了,因为如果每次都返回相同的值,则证明缓存是正常工作了.这种测试在之前那种简单的实现是不可能的.
分享到:
相关推荐
JAVA中用动态代理类实现记忆功能(二).rar
java中用数组为一个类定义多个对象,并对其进行实例化
JAVA中用GUI编程实现计算器模拟,并附带源代码。上传内容仅供参考。
java中用FileUtil实现文件读写
在java中用js 是实现代码树的显示
主要给大家介绍了关于在java中用ObjectMapper类实现Json与bean转换的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面跟着小编来一起学习学习吧。
Java语言使用hashmap实现向购物车添加删除修改商品,显示商品信息
java中用URLConnection类post方式提交表单的方法。
JAVA中用GUI编程实现计算器模拟.docxJAVA中用GUI编程实现计算器模拟.docxJAVA中用GUI编程实现计算器模拟.docxJAVA中用GUI编程实现计算器模拟.docxJAVA中用GUI编程实现计算器模拟.docxJAVA中用GUI编程实现计算器模拟....
包含java中经常使用的类,Application页面访问次数统计,MD5Code密码加密类,常用数据库分页语句,错误验证,动态级联菜单,网站计数器,国际化,sqlserver驱动包,搜索引擎等!
Java中用Calendar类计算周和周的起始日期
java及j2ee开发中常需要将对象转成json字符串进行数据传输,该包提供了JAVA对象和json字符串之间的转换方法。常见的类有JSONObject等
java中用FileUtil实现文件读写.pdf
(4)根据下面的要求实现圆类Circle。 ① 圆类Circle的成员变量:radius表示圆的半径。 ② 圆类Circle的方法成员: Circle():构造方法,将半径置0 Circle(double r):构造方法,创建Circle对象时将半径...
自己做的,能用栈实现括号匹配,程序很简单实用
java中用URLConnection类post方式提交表单.pdf
用JAVA实现的文件上传,控制台输入,保存到数据库
java中用Ganymed实现SCP和SFTP文件传输.pdf
java链接Access数据库实现简易通讯录(实现增删改功能)
用java实现动态验证码的效果,源代码可以直接拷贝到项目中用