Java中的记忆(Memoization)算法

JAVA herman 161浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

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));
 
	}
}

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

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Java中的记忆(Memoization)算法