记忆是衍生自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 { private byte runBBPAlgorithm(final int n) { } |
最简单直接的方法来缓存返回值可以通过修改这个类来实现:添加一个Map来保存之前计算得到的值,如下:
import java.util.HashMap; |