未加星标

斐波那契数列求和的js方案以及优化

字体大小 | |
[前端(javascript) 所属分类 前端(javascript) | 发布者 店小二03 | 时间 2016 | 作者 红领巾 ] 0人收藏点击收藏

在 codewars 上做了一道斐波那契数列求和的题目,做完之后做了一些简单的优化和用另一种方法实现。

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

以上函数使用递归的方式进行斐波那契数列求和,但效率十分低,很多值会重复求值。题目要求使用 memoization方案进行优化。

My Solution

memoization方案在《javascript模式》和《JavaScript设计模式》都有提到。memoization是一种将函数执行结果用变量缓存起来的方法。当函数进行计算之前,先看缓存对象中是否有次计算结果,如果有,就直接从缓存对象中获取结果;如果没有,就进行计算,并将结果保存到缓存对象中。

let fibonacci = (function() { let memory = [] return function(n) { if(memory[n] !== undefined) { return memory[n] } return memory[n] = (n === 0 || n === 1) ? n : fibonacci(n-1) + fibonacci(n-2) } })()

使用闭包实现的memoization函数。测试通过之后,突然我有一个小疑问,如果将memory的类型由数组换成对象,它的运算效率会有什么变化?于是,我将memory的类型换成了对象,并写了一个函数测试两种数据类型的运算效率。

function speed(n) { let start = performance.now() fibonacci(n) let end = performance.now() console.log(end - start) }

所有测试只在Chrome控制台测试,并且测试次数不多,结果不严谨,请多多包涵。

memory类型为数组时(单位:毫秒):

speed(500) // 0.8150000050663948 speed(5000) // 3.1799999997019768 speed(7500) // 4.234999991953373 speed(10000) // 8.390000000596046

memory类型为对象时(单位:毫秒):

speed(500) // 0.32499999552965164 speed(5000) // 1.6499999985098839 speed(7500) // 2.485000006854534 speed(10000) // 2.9999999925494194

虽然测试过程不严谨,但还是可以说明一点问题的。memory类型为对象是明显比类型为数组时,运算速度快很多。至于为什么对象操作比数组操作的速度快,请原谅我水平有限,暂时答不上来。(先挖好坑,以后回来填坑,逃)

Best Solution

别人的解决方案给了我灵感,让我想出了一个缓存效率高很多的方案。

var fibonacci = (function () { var memory = {} return function(n) { if(n==0 || n == 1) { return n } if(memory[n-2] === undefined) { memory[n-2] = fibonacci(n-2) } if(memory[n-1] === undefined) { memory[n-1] = fibonacci(n-1) } return memory[n] = memory[n-1] + memory[n-2] } })()

测试结果就不放了(因为我发现在Chrome控制台中运行测试代码时,输出结果不稳定)。不过,这里的缓存效率的确是提高了,前面的方案,一次计算最多缓存一个结果,而这个方案,一次计算最多缓存三个结果。从这个方面考虑,运算速度理论上是会比前面的方案快的。

动态规划解决方案

斐波那契数列求和除了可以用递归的方法解决,还可以用动态规划的方法解决。由于我是算法渣,对动态规划了解不多,只懂一点点皮毛,所以这里就不解释动态规划的概念了。(一不小心又挖了一个坑,逃)

直接贴代码好了:

function fibonacci(n) { let n1 = 1, n2 = 1, sum = 1 for(let i = 3; i <= n; i += 1) { sum = n1 + n2 n1 = n2 n2 = sum } return sum } 结语

只要注意细节,我们的代码还是有很大的优化空间的。有时候,你可能会疑惑,优化前后的性能没有明显的变化。我认为,那是你的应用规模或者数据量不够大而已,当它们大到一定程度的时候,优化的效果就很明显了。优化还是要坚持的,万一哪一天我们接手大型应用呢?

本文前端(javascript)相关术语:javascript是什么意思 javascript下载 javascript权威指南 javascript基础教程 javascript 正则表达式 javascript设计模式 javascript高级程序设计 精通javascript javascript教程

分页:12
转载请注明
本文标题:斐波那契数列求和的js方案以及优化
本站链接:http://www.codesec.net/view/480543.html
分享请点击:


1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责;
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性,不作出任何保证或承若;
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
技术大类 技术大类 | 前端(javascript) | 评论(0) | 阅读(21)