java中的Memoization实现_Implement Memoization in java

Memoization 在具有函数式编程特性的语言中用于缓存函数运算后的结果值,在java中可以使用动态代理实现这一特性,但对于java中的递归的运算,其不能缓存递归的过程值,而python,lisp等函数式特性的动态语言则能对每一次运算进行缓存.

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.


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(

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);//直接获取缓存值


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);//直接获取前面已经计算过的结果;;


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实现的文章:

Memoization in Java Using Dynamic Proxy Classes