JavaScript学习笔记之函数记忆
作者:冴羽 发布时间:2024-04-16 09:27:01
本文讲解函数记忆与菲波那切数列的实现,分享给大家,具体如下
定义
函数记忆是指将上次的计算结果缓存起来,当下次调用时,如果遇到相同的参数,就直接返回缓存中的数据。
举个例子:
function add(a, b) {
return a + b;
}
// 假设 memorize 可以实现函数记忆
var memoizedAdd = memorize(add);
memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数,第二次调用时,从缓存中取出数据,而非重新计算一次
原理
实现这样一个 memorize 函数很简单,原理上只用把参数和对应的结果数据存到一个对象中,调用时,判断参数对应的数据是否存在,存在就返回对应的结果数据。
第一版
我们来写一版:
// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
var cache = {};
return function(){
var key = arguments.length + Array.prototype.join.call(arguments, ",");
if (key in cache) {
return cache[key]
}
else return cache[key] = f.apply(this, arguments)
}
}
我们来测试一下:
var add = function(a, b, c) {
return a + b + c
}
var memoizedAdd = memorize(add)
console.time('use memorize')
for(var i = 0; i < 100000; i++) {
memoizedAdd(1, 2, 3)
}
console.timeEnd('use memorize')
console.time('not use memorize')
for(var i = 0; i < 100000; i++) {
add(1, 2, 3)
}
console.timeEnd('not use memorize')
在 Chrome 中,使用 memorize 大约耗时 60ms,如果我们不使用函数记忆,大约耗时 1.3 ms 左右。
注意
什么,我们使用了看似高大上的函数记忆,结果却更加耗时,这个例子近乎有 60 倍呢!
所以,函数记忆也并不是万能的,你看这个简单的场景,其实并不适合用函数记忆。
需要注意的是,函数记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,在客户端 JavaScript 中代码的执行时间复杂度往往成为瓶颈,因此在大多数场景下,这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。
第二版
因为第一版使用了 join 方法,我们很容易想到当参数是对象的时候,就会自动调用 toString 方法转换成 [Object object],再拼接字符串作为 key 值。我们写个 demo 验证一下这个问题:
var propValue = function(obj){
return obj.value
}
var memoizedAdd = memorize(propValue)
console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1
两者都返回了 1,显然是有问题的,所以我们看看 underscore 的 memoize 函数是如何实现的:
// 第二版 (来自 underscore 的实现)
var memorize = function(func, hasher) {
var memoize = function(key) {
var cache = memoize.cache;
var address = '' + (hasher ? hasher.apply(this, arguments) : key);
if (!cache[address]) {
cache[address] = func.apply(this, arguments);
}
return cache[address];
};
memoize.cache = {};
return memoize;
};
从这个实现可以看出,underscore 默认使用 function 的第一个参数作为 key,所以如果直接使用
var add = function(a, b, c) {
return a + b + c
}
var memoizedAdd = memorize(add)
memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6
肯定是有问题的,如果要支持多参数,我们就需要传入 hasher 函数,自定义存储的 key 值。所以我们考虑使用 JSON.stringify:
var memoizedAdd = memorize(add, function(){
var args = Array.prototype.slice.call(arguments)
return JSON.stringify(args)
})
console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7
如果使用 JSON.stringify,参数是对象的问题也可以得到解决,因为存储的是对象序列化后的字符串。
适用场景
我们以斐波那契数列为例:
var count = 0;
var fibonacci = function(n){
count++;
return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
fibonacci(i)
}
console.log(count) // 453
我们会发现最后的 count 数为 453,也就是说 fibonacci 函数被调用了 453 次!也许你会想,我只是循环到了 10,为什么就被调用了这么多次,所以我们来具体分析下:
当执行 fib(0) 时,调用 1 次
当执行 fib(1) 时,调用 1 次
当执行 fib(2) 时,相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次,共 1 + 1 + 1 = 3 次
当执行 fib(3) 时,相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次,共 3 + 1 + 1 = 5 次
当执行 fib(4) 时,相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次,共 5 + 3 + 1 = 9 次
当执行 fib(5) 时,相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次,共 9 + 5 + 1 = 15 次
当执行 fib(6) 时,相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次,共 15 + 9 + 1 = 25 次
当执行 fib(7) 时,相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次,共 25 + 15 + 1 = 41 次
当执行 fib(8) 时,相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次,共 41 + 25 + 1 = 67 次
当执行 fib(9) 时,相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次,共 67 + 41 + 1 = 109 次
当执行 fib(10) 时,相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次,共 109 + 67 + 1 = 177 次
所以执行的总次数为:177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次!
如果我们使用函数记忆呢?
var count = 0;
var fibonacci = function(n) {
count++;
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
fibonacci = memorize(fibonacci)
for (var i = 0; i <= 10; i++) {
fibonacci(i)
}
console.log(count) // 12
我们会发现最后的总次数为 12 次,因为使用了函数记忆,调用次数从 453 次降低为了 12 次!
兴奋的同时不要忘记思考:为什么会是 12 次呢?
从 0 到 10 的结果各储存一遍,应该是 11 次呐?咦,那多出来的一次是从哪里来的?
所以我们还需要认真看下我们的写法,在我们的写法中,其实我们用生成的 fibonacci 函数覆盖了原本了 fibonacci 函数,当我们执行 fibonacci(0) 时,执行一次函数,cache 为 {0: 0},但是当我们执行 fibonacci(2) 的时候,执行 fibonacci(1) + fibonacci(0),因为 fibonacci(0) 的值为 0, !cache[address]
的结果为 true,又会执行一次 fibonacci 函数。原来,多出来的那一次是在这里!
多说一句
也许你会觉得在日常开发中又用不到 fibonacci,这个例子感觉实用价值不高呐,其实,这个例子是用来表明一种使用的场景,也就是如果需要大量重复的计算,或者大量计算又依赖于之前的结果,便可以考虑使用函数记忆。而这种场景,当你遇到的时候,你就会知道的。
来源:https://segmentfault.com/a/1190000011033786?utm_source=tuicool&utm_medium=referral
猜你喜欢
- 一、引出问题假如有这两张表,它们中的课程可能价格不一样、周期不一样、等等...不一样...,现在有一张价格策略表,怎么就用一张表报保存它们之
- 前言面对计算密集型的任务,除了多进程,就是分布式计算,如何用 Python 实现分布式计算呢?今天分享一个很简单的方法,那就是借助于 Ray
- php统计数组元素个数count():对数组中的元素个数进行统计;sizeof():和count()具有同样的用途,这两个函数都可以返回数组
- 在上一篇Python接口自动化测试系列文章:Python接口自动化浅析yaml配置文件原理及用法,主要介绍主要介绍yaml语法、yaml存储
- MySQL中concat函数 使用方法:CONCAT(str1,str2,…)返回结果为连接参数产生的字符串。如有任何一个参数为NULL ,
- 前言最近在做项目的时候遇到一个问题,需要获取一个动态预览的图片的地址,这其实不是什么问题,主要是该图片的路径是写在css的backgroun
- path.makeUrlAbsolute() 把相对URL转化为绝对URLjQuery.mobile.path.makeUrlAbsolut
- 这两天一直在做课件,我个人一直不太喜欢PPT这个东西……能不用就不用,我个人特别崇尚极简风。谁让我们是程序员呢,所以就爱上了Jupyter写
- 在pycharm中我们有时需要切换python的版本,这里需要注意的是我们是在PyCharm中的Preferences中切换的,在File的
- 使用MySql的窗口函数统计数据时,发现一个小的问题,与大家一起探讨下。环境配置:mysql-installer-community-8.0
- 开发web应用程序是一件非常辛苦的事情,你需要花大把大把的时间来做无数的事情。假如你不运用有条理的方法,尤其是在复杂的项目中,你会承受忽视项
- 1.折线图 plt.plot()常用的一些参数:颜色(color):‘c’ 青红(cyan)&
- CentOS安装Python1.CentOS已经自带安装了2.x版本,先尝试python命令检查已安装的版本.如果你使用rpm、yum或de
- 每年的春节,都会有一些自己几乎没印象但父母就是很熟的亲戚,关系凌乱到你自己都说不清。今年趁着春节在家没事情干,正好之前知道有中国亲戚关系计算
- Oracle的系统要求 企业版:CPU最低PENTIUM200M推荐PENTIUMIII1G以上 内存最低128M推荐512M 硬盘空间系统
- 目录前言1. 效果图2. 原理3. 源码3.1 Numpy实现傅里叶变换3.2 OpenCV实现傅里叶变换3.3 HPF or LPF?参考
- 本文实例讲述了Python打开文件、文件读写操作、with方式、文件常用函数。分享给大家供大家参考,具体如下:打开文件:在python3中,
- def Num2MoneyFormat( change_number ): ""&q
- 1.下载PyQt官方网站:http://www.riverbankcomputing.com/software/pyqt/download5
- Python的json模块提供了一种很简单的方式来编码和解码JSON数据。 其中两个主要的函数是 json.dumps() 和 json.l