惰性求值——lodash源码解读

前言

lodash受欢迎的一个原因,是其优异的计算性能。而其性能能有这么突出的表现,很大部分就来源于其使用的算法——惰性求值。
本文将讲述lodash源码中,惰性求值的原理和实现。

一、惰性求值的原理分析

惰性求值(Lazy Evaluation),又译为惰性计算、懒惰求值,也称为传需求调用(call-by-need),是计算机编程中的一个概念,它的目的是要最小化计算机要做的工作
惰性求值中的参数直到需要时才会进行计算。这种程序实际上是从末尾开始反向执行的。它会判断自己需要返回什么,并继续向后执行来确定要这样做需要哪些值。

以下是How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.(如何提升Lo-Dash百倍算力?惰性计算的简介)文中的示例,形象地展示惰性求值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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),取出符合条件的数据:

1
2
3
4
5
6
[
{ name: 'Sunstone', price: 4 },
{ name: 'Sugilite', price: 7 },
{ name: 'Diopside', price: 3 },
{ name: 'Dioptase', price: 2 }
]

然后,执行take方法,提取前3个数据。

1
2
3
4
5
[
{ 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对数据进行逐个裁决
1
2
3
4
5
6
7
8
9
10
[
{ 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)代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
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方法

1
2
3
4
5
6
7
8
9
10
11
12
13
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进行标记。
这里还有一个技巧:

1
2
3
4
5
6
7
8
9
(function(){
// 私有方法
function filter(iteratee){
/* code */
}

// 绑定方法到原型链上
LazyWrapper.prototype.filter = filter;
})();

原型上的方法,先用普通的函数声明,然后再绑定到原型上。如果工具内部需要使用filter,则使用声明好的私有方法。
这样的好处是,外部如果改变LazyWrapper.prototype.filter,对工具内部,是没有任何影响的。

2.3 实现take方法

1
2
3
4
5
6
7
// 截取n个数据
function take(n){
this.__takeCount__ = n;
return this;
};

LazyWrapper.prototype.take = take;

2.4 实现value方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 惰性求值
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;

这里的一个重点就是:标签语句

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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 小检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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