lodash 受欢迎的一个原因, 是其优异的计算性能. 而其性能能有这么突出的表现, 很大部分就来源于其使用的算法 -- 惰性求值. 本文将讲述 lodash 源码中, 惰性求值的原理和实现.
一, 惰性求值的原理分析
惰性求值 (Lazy Evaluation), 又译为惰性计算, 懒惰求值, 也称为传需求调用 (call-by-need), 是计算机编程中的一个概念, 它的目的是要最小化计算机要做的工作. 惰性求值中的参数直到需要时才会进行计算. 这种程序实际上是从末尾开始反向执行的. 它会判断自己需要返回什么, 并继续向后执行来确定要这样做需要哪些值.
以下是 How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.(如何提升 Lo-Dash 百倍算力? 惰性计算的简介) 文中的示例, 形象地展示惰性求值.
- function priceLt(x) {
- return function(item) { return item.price <x; };
- }
- var gems = [
- { name: 'Sunstone', price: 4 },
- { name: 'Amethyst', price: 15 },
- { name: 'Prehnite', price: 20},
- { name: 'Sugilite', price: 7 },
- { name: 'Diopside', price: 3 },
- { name: 'Feldspar', price: 13 },
- { name: 'Dioptase', price: 2 },
- { name: 'Sapphire', price: 20 }
- ];
- var chosen = _(gems).filter(priceLt(10)).take(3).value();
复制代码
程序的目的, 是对数据集 gems 进行筛选, 选出 3 个 price 小于 10 的数据.
1.1 一般的做法
如果抛开 lodash 这个工具库, 让你用普通的方式实现
var chosen = _(gems).filter(priceLt(10)).take(3)
; 那么, 可以用以下方式:
_(gems) 拿到数据集, 缓存起来.
再执行 filter 方法, 遍历 gems 数组 (长度为 10), 取出符合条件的数据:
- [
- { name: 'Sunstone', price: 4 },
- { name: 'Sugilite', price: 7 },
- { name: 'Diopside', price: 3 },
- { name: 'Dioptase', price: 2 }
- ]
复制代码
然后, 执行 take 方法, 提取前 3 个数据.
- [
- { name: 'Sunstone', price: 4 },
- { name: 'Sugilite', price: 7 },
- { name: 'Diopside', price: 3 }
- ]
复制代码
总共遍历的次数为: 10+3. 执行的示例图如下:
1.2 惰性求值做法
普通的做法存在一个问题: 每个方法各做各的事, 没有协调起来浪费了很多资源.
如果能先把要做的事, 用小本本记下来, 然后等到真正要出数据时, 再用最少的次数达到目的, 岂不是更好.
惰性计算就是这么做的.
以下是实现的思路:
_(gems) 拿到数据集, 缓存起来
遇到 filter 方法, 先记下来
遇到 take 方法, 先记下来
遇到 value 方法, 说明时机到了
把小本本拿出来, 看下要求: 要取出 3 个数, price<10
使用 filter 方法里的判断方法 priceLt 对数据进行逐个裁决
[
{ name: 'Sunstone', price: 4 }, => priceLt 裁决 => 符合要求, 通过 => 拿到 1 个
{ name: 'Amethyst', price: 15 }, => priceLt 裁决 => 不符合要求
{ name: 'Prehnite', price: 20}, => priceLt 裁决 => 不符合要求
{ name: 'Sugilite', price: 7 }, => priceLt 裁决 => 符合要求, 通过 => 拿到 2 个
{ name: 'Diopside', price: 3 }, => priceLt 裁决 => 符合要求, 通过 => 拿到 3 个 => 够了, 收工!
- { name: 'Feldspar', price: 13 },
- { name: 'Dioptase', price: 2 },
- { name: 'Sapphire', price: 20 }
- ]
复制代码
如上所示, 一共只执行了 5 次, 就把结果拿到.
执行的示例图如下:
1.3 小结
从上面的例子可以得到惰性计算的特点:
延迟计算, 把要做的计算先缓存, 不执行
数据管道, 逐个数据通过 "裁决" 方法, 在这个类似安检的过程中, 进行过关的操作, 最后只留下符合要求的数据
触发时机, 方法缓存, 那么就需要一个方法来触发执行. lodash 就是使用 value 方法, 通知真正开始计算
二, 惰性求值的实现
依据上述的特点, 我将 lodash 的惰性求值实现进行抽离为以下几个部分:
2.1 实现延迟计算的缓存
实现_(gems). 我这里为了语义明确, 采用 lazy(gems) 代替.
- var MAX_ARRAY_LENGTH = 4294967295; // 最大的数组长度
- // 缓存数据结构体
- function LazyWrapper(value){
- this.__wrapped__ = value;
- this.__iteratees__ = [];
- this.__takeCount__ = MAX_ARRAY_LENGTH;
- }
- // 惰性求值的入口
- function lazy(value){
- return new LazyWrapper(value);
- }
复制代码
this.__wrapped__ 缓存数据
this.__iteratees__ 缓存数据管道中进行 "裁决" 的方法
this.__takeCount__ 记录需要拿的符合要求的数据集个数
这样, 一个基本的结构就完成了.
2.2 实现 filter 方法
- var LAZY_FILTER_FLAG = 1; // filter 方法的标记
- // 根据 筛选方法 iteratee 筛选数据
- function filter(iteratee){
- this.__iteratees__.push({
- 'iteratee': iteratee,
- 'type': LAZY_FILTER_FLAG
- });
- return this;
- }
- // 绑定方法到原型链上
- LazyWrapper.prototype.filter = filter;
复制代码
filter 方法, 将裁决方法 iteratee 缓存起来. 这里有一个重要的点, 就是需要记录 iteratee 的类型 type.
因为在 lodash 中, 还有 map 等筛选数据的方法, 也是会传入一个裁决方法 iteratee. 由于 filter 方法和 map 方法筛选方式不同, 所以要用 type 进行标记.
这里还有一个技巧:
- (function(){
- // 私有方法
- function filter(iteratee){
- /* code */
- }
- // 绑定方法到原型链上
- LazyWrapper.prototype.filter = filter;
- })();
复制代码
原型上的方法, 先用普通的函数声明, 然后再绑定到原型上. 如果工具内部需要使用 filter, 则使用声明好的私有方法.
这样的好处是, 外部如果改变
LazyWrapper.prototype.filter
, 对工具内部, 是没有任何影响的.
2.3 实现 take 方法
- // 截取 n 个数据
- function take(n){
- this.__takeCount__ = n;
- return this;
- };
- LazyWrapper.prototype.take = take;
复制代码
2.4 实现 value 方法
- // 惰性求值
- function lazyValue(){
- var array = this.__wrapped__;
- var length = array.length;
- var resIndex = 0;
- var takeCount = this.__takeCount__;
- var iteratees = this.__iteratees__;
- var iterLength = iteratees.length;
- var index = -1;
- var dir = 1;
- var result = [];
- // 标签语句
- outer:
- while(length-- && resIndex < takeCount){
- // 外层循环待处理的数组
- index += dir;
- var iterIndex = -1;
- var value = array[index];
- while(++iterIndex < iterLength){
- // 内层循环处理链上的方法
- var data = iteratees[iterIndex];
- var iteratee = data.iteratee;
- var type = data.type;
- var computed = iteratee(value);
- // 处理数据不符合要求的情况
- if(!computed){
- if(type == LAZY_FILTER_FLAG){
- continue outer;
- }else{
- break outer;
- }
- }
- }
- // 经过内层循环, 符合要求的数据
- result[resIndex++] = value;
- }
- return result;
- }
- LazyWrapper.prototype.value = lazyValue;
复制代码
这里的一个重点就是: 标签语句
- outer:
- while(length-- && resIndex < takeCount){
- // 外层循环待处理的数组
- index += dir;
- var iterIndex = -1;
- var value = array[index];
- while(++iterIndex < iterLength){
- // 内层循环处理链上的方法
- var data = iteratees[iterIndex];
- var iteratee = data.iteratee;
- var type = data.type;
- var computed = iteratee(value);
- // 处理数据不符合要求的情况
- if(!computed){
- if(type == LAZY_FILTER_FLAG){
- continue outer;
- }else{
- break outer;
- }
- }
- }
- // 经过内层循环, 符合要求的数据
- result[resIndex++] = value;
- }
复制代码
当前方法的数据管道实现, 其实就是内层的 while 循环. 通过取出缓存在 iteratees 中的裁决方法取出, 对当前数据 value 进行裁决.
如果裁决结果是不符合, 也即为 false. 那么这个时候, 就没必要用后续的裁决方法进行判断了. 而是应该跳出当前循环.
而如果用 break 跳出内层循环后, 外层循环中的
result[resIndex++] = value;
还是会被执行, 这是我们不希望看到的.
应该一次性跳出内外两层循环, 并且继续外层循环, 才是正确的.
标签语句, 刚好可以满足这个要求.
2.5 小检测
- var testArr = [1, 19, 30, 2, 12, 5, 28, 4];
- lazy(testArr)
- .filter(function(x){
- console.log('check x='+x);
- return x < 10
- })
- .take(2)
- .value();
- // 输出如下:
- check x=1
- check x=19
- check x=30
- check x=2
- // 得到结果: [1, 2]
复制代码
2.6 小结
整个惰性求值的实现, 重点还是在数据管道这块. 以及, 标签语句在这里的妙用. 其实实现的方式, 不只当前这种. 但是, 要点还是前面讲到的三个. 掌握精髓, 变通就很容易了.
结语
惰性求值, 是我在阅读 lodash 源码中, 发现的最大闪光点.
当初对惰性求值不甚理解, 想看下 javascript 的实现, 但网上也只找到上文提到的一篇文献.
那剩下的选择, 就是对 lodash 进行剖离分析. 也因为这, 才有本文的诞生.
希望这篇文章能对你有所帮助. 如果可以的话, 给个 star
最后, 附上本文实现的简易版 lazy.js 完整源码: https://github.com/wall-wxk/blogDemo/blob/master/lodash/lazy.js
来源: http://www.mzh.ren/lodash-lazy-evaluation.html