你的位置:首页 > Java教程

[Java教程]memoization提升递归效率


从开通博客到目前为止,也有一年了,刚开始的写了一篇工作的感想,然后就一直不知道写什么,看园子里的文章实在是很专业,怕自己写的太水。但是,写一些东西总归是好的,于是就当作是记笔记一样,开始写第一篇技术类的文章。

最近打算巩固加强javascript知识,所以开始做codewars, 通过解决codewars的kata,真的了解了一些没有注意的知识点。最近就了解了一下,以前没有听过的memoization.

codewars的题目是这样写的:

给一个整数n,写一个函数返回fibonacci数列的第n个数,并且不希望执行函数后还要去泡杯咖啡来等待结果~囧~,然后提出了'implement the memoization solution'。由于之前没有听说过memoization,所以就去google了一下了解到底什么是memoization。

 

一  memoization简介

 

维基百科是这样描述的:

memoization最初是用来优化计算机程序使之计算的更快的技术,是通过存储调用函数的结果并且在同样参数传进来的时候返回结果。大部分应该是在递归函数中使用。

memoization这个词是在1968年被Donald Michie创造出来的,它源于拉丁语memoradum,在英语中通常简写为memo,因此就有了将一个函数的返回结果暂存入某个变量中的意思。(翻译水平略渣,如有不对,欢迎指正拍砖)。

 

二  通过Fibonacci例子进一步了解

 

一般实现输出fibonacci数列第n个数,应该使用递归调用,代码是这样的:

function fibonacci(n){  if(n==0||n==1){    return n;  }  return fibonacci(n-1) + fibonacci(n-1);}    

由于递归函数会重复调用很多遍函数,传入同样的参数,得到同样的结果,实际是重复实现同一个行为,就会导致效率很低。比如执行fibonacci(5),就要先算出fibonacci(4)和fibonacci(3);而计算fibonacci(4)和fibonacci(3),就要计算fibonacci(3),fibonacci(2)和fibonacci(2),fibonacci(1),这就像一个树一样,每个分支都要重复计算,直到得到fibonacci(1)为止。如下图所示: 

 

这样就会导致需要计算很多遍的重复数据,于是想到是否能够把已经计算过的结果暂时存起来,等到下次用的时候直接取出结果。所以定义了一个数组用来存放计算过的数据,然后在需要的时候从数组中查询,这样就会省去不需要的计算,提高程序的效率。代码如下:

var fibonacci = (function(){ var cache = [];           //定义一个空的存放缓存的数组 return function(n){        if(n === 0 || n === 1){   return n;  }else{   cache[n-1] = cache[n-1]||fibonacci(n-1); //先从cache数组里查询结果,如果没找到的话在计算   cache[n-2] = cache[n-2]||fibonacci(n-2);   return cache[n-1]+cache[n-2];  } }})();

三 总结

memorization 可以把函数每次的返回值存在一个数组或者对象中,在接下来的计算中可以直接读取已经计算过并且返回的数据,不用重复多次相同的计算。这种方法可用于部分递归中以提高递归的效率。

最后,本文如果有任何有问题的地方,欢迎批评指正。