Java中的记忆(Memoization)算法

Memoization 被很多人翻译成记忆，是根据字面意思来翻译的。今天我就来说一说记忆化算法。

它其实是一种很巧妙的思想或设计，被称为算法，我想主要是因为它经常会和一些算法进行搭配使用吧。

Memoization 应该有很大的使用场景的，举个例子。我们现在要算一个斐波那契数列，对于一个已经算过的数，就没必要再进行计算一遍了。我们可以把这个数之前算过的结果从缓存中取出来。

比如类似下面的斐波那契数列。

0,1,1,2,3,5,8,13,21,34,55,89,144 ..

它们具有以下递归关系：

F（n）= F（n-1）+ F（n-2）

在 Java 中我们可以靠递归函数来实现。

// Fibonacci without Memoization
public int fibonacci(int n){
	
	if( n == 0 ) return 0;
	if( n == 1 ) return 1;
	
	System.out.println("Calculating fibonacci number for: "+n);
	return (fibonacci(n-1) + fibonacci(n-2));	
}

现在，我们可以输入任意数进行计算。但是，当我重复计算一个数时，它并没有记忆，并没有记住上次对该数计算对结果。还是会一层一层的递归计算。

解决这类问题的办法就是，采用缓存，把之前计算过的数字直接缓存起来。下次再调用就先判断缓存中是否有没有，没有的化再计算，否则直接从缓存中读取。

public class FibonacciMemoizationAlgorithm {
	private Map<Integer, Integer> memoizeTable = new HashMap<>(); // O(1)
	// Fibonacci with Memoization
	public int fibonacciMemoize(int n){
		if( n == 0 ) return 0;
		if( n == 1 ) return 1;
		if( this.memoizeTable.containsKey(n) ) {
			System.out.println("Getting value from computed result for "+n);
			return this.memoizeTable.get(n);
		}
		int result = fibonacciMemoize(n-1)+ fibonacciMemoize(n-2);
		System.out.println("Putting result in cache for "+n);
		this.memoizeTable.put(n, result);
		return result;
	}
	// Fibonacci without Memoization
	public int fibonacci(int n){
		if( n == 0 ) return 0;
		if( n == 1 ) return 1;
		System.out.println("Calculating fibonacci number for: "+n);
		return (fibonacci(n-1) + fibonacci(n-2));	
	}
	public static void main(String[] args) {
		FibonacciMemoizationAlgorithm fibonacciAlgorithm = new FibonacciMemoizationAlgorithm();
		System.out.println("Fibonacci value for n=5:  "+fibonacciAlgorithm.fibonacciMemoize(5));
 
	}
}

这就是记忆化的原理，不同的场景采用的缓存技术不同，但原理基本都类似。

： » Java中的记忆(Memoization)算法