Memoization 在具有函数式编程特性的语言中用于缓存函数运算后的结果值,在java中可以使用动态代理实现这一特性，但对于java中的递归的运算,其不能缓存递归的过程值,而python,lisp等函数式特性的动态语言则能对每一次运算进行缓存.
Memoization的简单介绍如下:
我们在第一次计算一个值后就记录一个值.然后在后续问题中使用这个值.
we record a value the first time it’s computed,then look it up the subsequent times we need it.
这就是动态编程这种通用技术的核心
And this is what lies at the heart of this very general technique called dynamic programming.
实际上 它也是很多保存结果的计算技巧的核心
And in fact,it lies at the heart of a lot of useful computational techniques where we save results.
java具体的类可以这样实现:
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);
System.out.println(“get cache value ===”+value);
if (value == null && !cache.containsKey(key)) {
value = invoke(method, args);
System.out.println(“put cache value ===”+key +”–”+value);
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;
}
}
然后可以构造一个接口:
public interface Car {
public int fibonacci(int n);
}
一个实现类:
public class CarImpl implements Car {
public int fibonacci(int n) {
if (n == 0 || n == 1)
return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
在调用时候:
Car foo = (Car) Memoizer.memoize(new CarImpl());
int n = foo.fibonacci(5);//直接运算并对结果进行缓存
int rr = foo.fibonacci(6);//直接运算并对结果进行缓存，不能够获取fibonacci(5)的结果值
但是若:
int n = foo.fibonacci(5);//直接运算并对结果进行缓存
int rr = foo.fibonacci(5);//直接获取缓存值
但在函数式特性的语言中(javascript):
function memoize(fundamental, cache){
cache = cache || {};
var shell = function(arg){
if (!cache.hasOwnProperty(arg)){
cache[arg] = fundamental(arg);
}
return cache[arg];
};
return shell;
}
function factorial(n){
if (n==0 || n==1){ return 1;}
return factorial(n-1)+factorial(n-2);
}
//memoize the factorial function
var memfactorial = memoize(factorial, { 0: 1, 1: 1 });
//call the new function
var fact6 = memfactorial(6);
var fact5 = memfactorial(5);//直接获取前面已经计算过的结果
console.info(fact6);
console.info(fact5);
wiki中对Memoization的介绍:
In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs. Memoization has also been used in other contexts (and for purposes other than speed gains), such as in simple mutually recursive descent parsing[1] in a general top-down parsing algorithm[2][3] that accommodates ambiguity and left recursion in polynomial time and space. Although related to caching, memoization refers to a specific case of this optimization, distinguishing it from forms of caching such as buffering or page replacement. In the context of some logic programming languages, memoization is also known as tabling;[4] see also lookup table.
关于java Memoization实现的文章: