提升JavaScript的运行速度,递归是拖慢脚本运行速度的大敌之一。太多的递归会让浏览器变得越来越慢直到死掉或者莫名其妙的突然自动退出(在firefox中弹出脚本无响应的对话框),所以我们一定要解决在JavaScript中出现的这一系列性能问题。在这个系列文章的第二篇中,我曾经简短的介绍了如何通过 memorization技术来替代函数中太多的递归调用。memoization是一种可以缓存之前运算结果的技术,这样我们就不需要重新计算那些已经计算过的结果。对于通过递归来进行计算的函数,memoization简直是太有用了。我现在使用的memoizer是由Crockford写的,主要应用在那些返回整数的递归运算中。当然并不是所有的递归函数都返回整数,所以我们需要一个更加通用的memoizer()函数来处理更多类型的递归函数。
function memoizer(fundamental, cache){ cache = cache || {} var shell = function(arg){ if (!(arg in cache)){ cache[arg] = fundamental(shell, arg) } return cache[arg]; }; return shell;}这个版本的函数和Crockford写的版本有一点点不同。首先,参数的顺序被颠倒了,原有函数被设置为第一个参数,第二个参数是缓存对象,为可选参数,因为并不是所有的递归函数都包含初始信息。在函数内部,我将缓存对象的类型从数组转换为对象,这样这个版本就可以适应那些不是返回整数的递归函数。在shell函数里,我使用了in操作符来判断参数是否已经包含在缓存里。这种写法比测试类型不是undefined更加安全,因为 undefined是一个有效的返回值。我们还是用之前提到的斐波纳契数列来做说明:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0":0, "1":1});同样的,执行fibonacci(40)这个函数,只会对原有的函数调用40次,而不是夸张的331,160,280次。 memoization对于那些有着严格定义的结果集的递归算法来说,简直是棒极了。然而,确实还有很多递归算法不适合使用memoization方法来进行优化。
我在学校时的一位教授一直坚持认为,任何使用递归的情况,如果有需要,都可以使用迭代来代替。实际上,递归和迭代经常会被作为互相弥补的方法,尤其是在另外一种出问题的情况下。将递归算法转换为迭代算法的技术,也是和开发语言无关的。这对 JavaScript来说是很重要的,因为很多东西在执行环境中是受到限制的(the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive.)。让我们回顾一个典型的递归算法,比如说归并排序,在JavaScript中实现这个算法需要下面的代码:
function merge(left, right){ var result = []; while (left.length > 0 && right.length > 0){ if (left[0] < right[0]){ result.push(left.shift()); } else { result.push(right.shift()); } } return result.concat(left).concat(right);}//采用递归实现的归并排序算法function mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2), left = items.slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));}调用mergeSort()函数处理一个数组,就可以返回经过排序的数组。注意每次调用mergeSort()函数,都会有两次递归调用。这个算法不可以使用memoization来进行优化,因为每个结果都只计算并使用一次,就算缓冲了结果也没有什么用。如果你使用mergeSort()函数来处理一个包含100个元素的数组,总共会有199次调用。1000个元素的数组将会执行1999次调用。在这种情况下,我们的解决方案是将递归算法转换为迭代算法,也就是说要引入一些循环(关于算法,可以参考这篇《List Processing: Sort Again, Naturally》)。
分享到:
相关推荐
计算机视觉Github开源论文 Meta-Learning without Memorization
Use an interactive program for memorization, practice, and correction, with 89 examples, full TOC. 资料来自互联网,仅供借鉴,请保护作者及出版商知识产权。
在cards/ 目录中,您会注意到已经有一个json (.js) 文件。 您可以将其用作模板。 下面是一个典型的 json 文件应该是什么样子的一般分类: var memory = { groups : [ { group : <groupname> , cards : [ ...
Efficient Computation Reduction in Bayesian Neural Networks through Feature Decomposition and Memorization
当主耶稣基督的跟随者对他的话语和他儿子的拯救信息的知识增长时,上帝很高兴。 背诵经文是值得称赞的,但初学者可能会发现它令人生畏。 InVerse 用 15,300 个预加载的诗句简化了这一点
powermem是一个可帮助用户记住事实集合的应用程序。 它快速,易于扩展(使用Python),支持从外部数据源(如字典)导入,并提供详细的统计信息,以便用户可以绘制进度图。
可用脚本在项目目录中,可以运行:yarn start 在开发模式下运行应用程序。 打开在浏览器中查看它。 如果您进行编辑,则页面将重新加载。 您还将在控制台中看到任何棉绒错误。yarn test 在交互式监视模式下启动测试...
Put it all together with the Zebreto effective-memorization flashcard app Deploy apps to the iOS App Store and Google’s Play Store Paperback: 272 pages Publisher: O'Reilly Media; 1 edition (December...
记忆工具 来自培训任务
Become a SuperLearner - Learn Speed Reading & Advanced Memorization
本项目会将用户查询的所有单词储存在本地.csv文件中,再次查询时可以直接调用,减少api消耗 请使用以下格式查询 instruct--task:subtask 例如: exotic--vocab:mem 运行 cd word-memorization python3 VocabGPT.py...
Decorebator应用程式 基于上下文的记忆应用程序,可扩展您的词汇量 目标 通过以上下文为中心的方式,帮助语言学习者获得新的表达,习语和词汇。 我个人厌倦了无聊的记忆应用程序,这些应用程序在... JavaScript / ES
主要介绍了提升Python效率之使用循环机制代替递归函数的相关知识,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
1.Unlimited memorization of words 2.Time September 14, 2020 3.No need to log in to use 4.OPPO tested, Redmi Android version available
This Study Guide has been carefully written and compiled by ...learn the concepts behind the questions rather than be a strict memorization tool. Repeated readings will increase your comprehension.
This book instructs you in Python by slowly building and establishing skills through techniques such as practice and memorization, then applying them to increasingly di cult problems. By the end of ...
Neural networks are great at memorization and not (yet) great at reasoning. Hope for Reinforcement Learning: Brute-force propagation of outcomes to knowledge about states and actions. This is a kind ...
学习实例 habit_tracker word_memorization_game plicate_files_deleter
We then explain the concept of memorization and infinite sequences for on-demand computation. Further, the book takes you through Scala’s stackable traits and dependency injection, a popular ...