前端培訓之lazy.js 惰性求值實現(xiàn)分析
來看一個 lazy.js 主頁提供的示例：
1
2
3
4
5
6 |
var people = getBigArrayOfPeople();
var results = _.chain(people)
.pluck('lastName')
.filter(function(name) { return name.startsWith('Smith'); })
.take(5)
.value(); |
上例中，要在非常非常多的人里面，找出 5 個以 Smith 開頭的 lastName。如果在上面的 pluck() 和 filter() 的過程中，每一步都產生了臨時數(shù)組，也就是說對上一步返回的數(shù)據(jù)執(zhí)行了一次循環(huán)、處理的過程，那么整個查找的過程可能會花費很長的時間。
不采用上面的這種寫法，單純?yōu)榱诵阅芸紤]，可以這樣處理：
1
2
3
4
5
6
7
8
9
10 |
var results = [];
for (var i = 0; i < people.length; ++i) {
var lastName = people[i].lastName;
if (lastName.startsWith('Smith')) {
results.push(value);
if (results.length === 5) {
break;
}
}
} |
首先，對于原始數(shù)據(jù)，只做一次循環(huán)，單次循環(huán)中完成所有的計算。其次，由于只需要 5 個最終結果，所以，一旦得到了 5 個結果，就終止循環(huán)。
采取這種處理方法，對于比較大的數(shù)組，在計算性能上應該會有明顯的提升。
不過，如果每次遇到這種類似的情形，為了性能，都要手寫這樣的代碼，有點麻煩，而且代碼不清晰，不便于理解、維護。第一個例子中的寫法要好些，明顯更易讀一些，但是對于性能方面有些擔憂。
所以，如果可以結合第一個例子中的寫法，但又能有第二個例子中的性能提升，豈不是很好？
接下來再說說“惰性求值”了。
Lazy evaluation – wikipedia
https://en.wikipedia.org/wiki/Lazy_evaluation
In
programming language theory,
lazy evaluation, or
call-by-need is an
evaluation strategy which delays the evaluation of an
expression until its value is needed (
non-strict evaluation) and which also avoids repeated evaluations (
sharing).
用我的話來表達，惰性求值就是：
對于一個表達式，在不需要值的時候不計算，需要的時候才計算。
JavaScript 并非從語言層面就支持這樣的特性，而是要通過一些技術來模擬、實現(xiàn)。
首先，不能是表達式，表達式在 JS 中是立即求值的。所以，要像第一個例子中的那樣，將求值的過程包裝為函數(shù)，只在需要求值的時候才調用該函數(shù)。
然后，延遲計算還需要通過“精妙的”設計和約定來實現(xiàn)。對于第一個例子，pluck()、filter()、take() 方法在調用時，不能直接對原始數(shù)據(jù)進行計算，而是要延遲到類似 value() 這樣的方法被調用時再進行。
在分析 Lazy.js 的惰性求值實現(xiàn)前，先總結下這里要討論的借助惰性求值技術來實現(xiàn)的目標：
而對于 Lazy.js 中的惰性求值實現(xiàn)，可以總結為：
- 收集計算需求
- 延遲并優(yōu)化計算的執(zhí)行過程
分析：Lazy.js 的惰性求值實現(xiàn)
與 Underscore、Lo-Dash 不同，Lazy.js 只提供鏈式的、惰性求值的計算模式，這也使得其惰性求值實現(xiàn)比較“純粹”，接下來就進入 Lazy.js 的實現(xiàn)分析了。
先看下使用 Lazy.js 的代碼（來自
simply-lazy – demo）：
1
2
3
4
5
6
7
8
9
10 |
Lazy([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
.map(i => i * 2)
.filter(i => i <= 10)
.take(3)
.each(i => print(i))
// output:
// 2
// 4
// 6 |
注：為了書寫方法，函數(shù)定義采用 ES6 的 “=>” 語法。
這是一個有點無聊的例子，對 1 – 10 先進行乘 2 運算，然后過濾出小于 10 的值，再取前 3 個結果值輸出。
如果對上述代碼的執(zhí)行進行監(jiān)測（參考：
借助 Proxy 實現(xiàn)回調函數(shù)執(zhí)行計數(shù)），會得到以下結果：
demo – simply-lazy
map() 和 filter() 的過程都只執(zhí)行了 3 次。
先關注 map() 調用，顯然，這里沒有立即執(zhí)行計算，因為這里的代碼還不能預知到后面的 filter() 和 take(3)，所以不會聰明地知道自己只需要執(zhí)行 3 次計算就可以了。如果沒有執(zhí)行計算，那么這里做了什么，又返回了什么呢？
先說答案：其實從 Lazy() 返回的是一個 Sequence 類型的對象，包含了原始的數(shù)據(jù)；map() 方法執(zhí)行后，又生成了一個新的 Sequence 對象，該對象鏈接到上一個 Sequence 對象，同時記錄了當前步驟要執(zhí)行的計算（i => i * 2），然后返回新的 Sequence 對象。后續(xù)的 filter() 和 take() 也是類似的過程。
上面的代碼也可以寫成：
1
2
3
4
5
6
7 |
var seq0 = Lazy([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
var seq1 = seq0.map(i => i * 2)
var seq2 = seq1.filter(i => i <= 10)
var seq3 = seq2.take(3)
// 求值
seq3.each(i => print(i)) |
在最后一個求值時，已經(jīng)有一個 Sequence 鏈了：
| 1 |
seq0 <- seq1 <- seq2 <- seq3 |
在 seq3 調用 each() 方法執(zhí)行求值前，這些鏈上的 seq 都還沒有執(zhí)行計算。那么計算的過程是怎樣的呢？其實就類似于最前面第二個例子那樣，在一個循環(huán)中，由鏈上的最后一個 seq 開始，依次向前面一個 seq 獲取值，再將值返回給調用方（也就是下一個 seq）前，會應用當前 seq 的計算。
獲得第一個最終結果值的過程為：
1
2
3
4
5
6 |
[1] seq3 調用 seq2 獲取第 1 個值
[2] seq2 調用 seq1 獲取第 1 個值
[3] seq1 直接從 seq0 的 source 屬性對應的原始數(shù)值取值（第 1 個值為 1）
[4] seq1 得到 1，應用計算（i => i * 2），得到 2，返回給調用方（seq2）
[5] seq2 得到 2，應用計算（i => i < 10），滿足條件，將 2 返回給調用方（seq3）
[6] seq3 得到 2，應用計算（已返回值數(shù)目是否小于 3），滿足條件，將 2 返回給調用方（seq3.each） |
最終，seq3.each() 得到第 1 個值（2），應用計算（i => print(i)），將其輸出。然后繼續(xù)獲取下一個值，直到在某個過程中調用終止（這里是 take() 計算中已返回 3 個值時終止）。
除了 map()、filter()、take()，Lazy.js 還提供了更多的計算模式，不過其惰性計算的過程就是這樣了，總結為：
- Lazy() 返回初始的 Sequence 對象
- 惰性計算方法返回新的 Sequence 對象，內部記錄上一個 Sequence 對象以及當前計算邏輯
- 求值計算方法從當前 Sequence 對象開始，依次向上一個 Sequence 對象獲取值
- Sequence 對象在將從上一個 Sequence 對象獲得的值返回給下一個 Sequence 前，應用自身的計算邏輯
Lazy.js 的 Sequence 的設計，使得取值和計算的過程形成一個長鏈，鏈條上的單個節(jié)點只需要完成上傳、下達，并且應用自身計算邏輯就可以了，它不需要洞悉整體的執(zhí)行過程。每個節(jié)點各司其職，最終實現(xiàn)了惰性計算。
代碼有時候勝過萬語千言，下面通過對簡化版的 Lazy.js（
simply-lazy）的源碼分析，來更進一步展示 Lazy.js 惰性計算的原理。
實現(xiàn)：簡化版的 Lazy.js
Lazy.js 可以支持進行計算的數(shù)據(jù)，除了數(shù)組，還有字符串和對象。simply-lazy 只提供了數(shù)組的支持，而且只支持三種惰性求值方法：
分別看這個三個方法的實現(xiàn)。
（一）map
Lazy() 直接返回的 Sequence 對象是比較特殊的，和鏈上的其他 Sequence 對象不同，它已經(jīng)是根節(jié)點，自身記錄了原始數(shù)據(jù)，也不包含計算邏輯。所以，對這個對象進行遍歷其實就是遍歷原始數(shù)據(jù)，也不涉及惰性計算。
simple-lazy 中保留了 Lazy.js 中的命名方式，盡管只支持數(shù)組，還是給這個類型取名為 ArrayWrapper：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
function ArrayWrapper(source) {
var seq = ArrayLikeSequence()
seq.source = source
seq.get = i => source[i]
seq.length = () => source.length
seq.each = fn => {
var i = -1
var len = source.length
while (++i < len) {
if (fn(source[i], i) === false) {
return false
}
}
return true
}
seq.map = mapFn => MappedArrayWrapper(seq, mapFn)
seq.filter = filterFn => FilteredArrayWrapper(seq, filterFn)
return seq
} |
simple-lazy 為了簡化代碼，并沒有采用 Lazy.js 那種為不同類型的 Sequence 對象構造不同的類的模式，Sequence 可以看作普通的對象，只是按照約定，需要支持幾個接口方法而已。像這里的 ArrayWrapper()，返回的 seq 對象盡管來自 ArrayLikeSequence()，但自身已經(jīng)實現(xiàn)了大多數(shù)的接口。
Lazy 函數(shù)其實就是返回了這樣的 ArrayWrapper 對象：
1
2
3
4
5
6 |
function Lazy(source) {
if (source instanceof Array) {
return ArrayWrapper(source);
}
throw new Error('Sorry, only array is supported in simply-lazy.')
} |
如果對于 Lazy() 返回的對象之間進行求值，可以看到，其實就是執(zhí)行了在 ArrayWrapper 中定義的遍歷原始數(shù)據(jù)的過程。
下面來看 seq.map()。ArrayWrapper 的 map() 返回的是 MappedArrayWrapper 類型的 Sequence 對象：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 |
function MappedArrayWrapper(parent, mapFn) {
var source = parent.source
var length = source.length
var seq = ArrayLikeSequence()
seq.parent = parent
seq.get = i => (i < 0 || i >= length) ? undefined : mapFn(source[i])
seq.length = () => length
seq.each = fn => {
var i = -1;
while (++i < length) {
if (fn(mapFn(source[i], i), i) === false) {
return false
}
}
return true
}
return seq
} |
這其實也是個特殊的 Sequence（所以名字上沒有 Sequence），因為它知道自己上一級 Sequence 對象是不包含計算邏輯的原始 Sequence 對象，所以它直接通過 parent.source 就可以獲取到原始數(shù)據(jù)了。
此時執(zhí)行的求值，則是直接在原始數(shù)據(jù)上應用傳入的 mapFn。
而如果是先執(zhí)行了其他的惰性計算方法，對于得到的結果對象再應用 map() 呢， 這個時候就要看具體的情況了，simply-lazy 中還有兩種相關的類型：
- MappedSequence
- IndexedMappedSequence
MappedSequence 是更通用的類型，對應 map() 得到 Sequence 的類型：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 |
function MappedSequence(parent, mapFn) {
var seq = new Sequence()
seq.getIterator = () => {
var iterator = parent.getIterator()
var index = -1
return {
current() { return mapFn(iterator.current(), index) },
moveNext() {
if (iterator.moveNext()) {
++index
return true
}
return false
}
}
}
seq.each = fn => parent.each((e, i) => fn(mapFn(e, i), i))
return seq
} |
來看這里的求值（each）過程，是間接調用了其上級 Sequence 的 each() 來完成的。同時還定義了 getIterator() 接口，使得其下級 Sequence 可以從這里得到一個迭代器，對于該 Sequence 進行遍歷。迭代器在 Lazy.js 中也是一個約定的協(xié)議，實現(xiàn)該協(xié)議的對象要支持 current() 和 moveNext() 兩個接口方法。從迭代器的邏輯中，可以看到，當 MappedSequence 對象作為其他 Sequence 的上級時，如果實現(xiàn)“上傳下達”。
而 IndexedMappedSequence 的實現(xiàn)要簡單些，它的主要功能都來源于“繼承” ：
1
2
3
4
5
6
7
8
9
10
11 |
function IndexedMappedSequence(parent, mapFn) {
var seq = ArrayLikeSequence()
seq.parent = parent
seq.get = (i) => {
if (i < 0 || i >= parent.length()) {
return undefined;
}
return mapFn(parent.get(i), i);
}
return seq
} |
IndexedMappedSequence 只提供了獲取特定索引位置的元素的功能，其他的處理交由 ArrayLikeSequence 來實現(xiàn)。
而 ArrayLikeSequence 則又“繼承”自 Sequence：
1
2
3
4
5
6
7 |
function ArrayLikeSequence() {
var seq = new Sequence()
seq.length = () => seq.parent.length()
seq.map = mapFn => IndexedMappedSequence(seq, mapFn)
seq.filter = filterFn => IndexedFilteredSequence(seq, filterFn)
return seq
} |
Sequence 中實現(xiàn)的是更一般意義上的處理。
上面介紹的這些與 map 有關的 Sequence 類型，其實現(xiàn)各有不同，的確有些繞。但無論是怎樣進行實現(xiàn)，其核心的邏輯沒有變，都是要在其上級 Sequence 的值上應用其 mapFn，然后返回結果值給下級 Sequence 使用。這是 map 計算的特定模式。
（二）filter
filter 的計算模式與 map 不同，filter 對上級 Sequence 返回的值應用 filterFn 進行判斷，滿足條件后再傳遞給下級 Sequence，否則繼續(xù)從上級 Sequence 獲取新一個值進行計算，直到?jīng)]有值或者找到一個滿足條件的值。
filter 相關的 Sequence 類型也有多個，這里只看其中一個，因為盡管實現(xiàn)的方式不同，其計算模式的本質是一樣的：
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 |
function FilteredSequence(parent, filterFn) {
var seq = new Sequence()
seq.getIterator = () => {
var iterator = parent.getIterator()
var index = 0
var value
return {
current() { return value },
moveNext() {
var _val
while (iterator.moveNext()) {
_val = iterator.current()
if (filterFn(_val, index++)) {
value = _val
return true
}
}
value = undefined
return false
}
}
}
seq.each = fn => {
var j = 0;
return parent.each((e, i) => {
if (filterFn(e, i)) {
return fn(e, j++);
}
})
}
return seq
} |
FilteredSequence 的 getIterator() 和 each() 中都可以看到 filter 的計算模式，就是前面說的，判斷上級 Sequence 的值，根據(jù)結果決定是返回給下一級 Sequence 還是繼續(xù)獲取。
不再贅述。
（三）take
take 的計算模式是從上級 Sequence 中獲取值，達到指定數(shù)目就終止計算：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 |
function TakeSequence(parent, count) {
var seq = new Sequence()
seq.getIterator = () => {
var iterator = parent.getIterator()
var _count = count
return {
current() { return iterator.current() },
moveNext() { return (--_count >= 0) && iterator.moveNext() }
}
}
seq.each = (fn) => {
var _count = count
var i = 0
var result
parent.each(e => {
if (i < count) { result = fn(e, i++); }
if (i >= count) { return false; }
return result
})
return i === count && result !== false
}
return seq
} |
只看 TakeSequence 類型，與 FilteredSequence 類似，其 getIterator() 和 each() 中都提現(xiàn)了其計算模式。一旦獲得了指定數(shù)目的值，就終止計算（通過 return false）。
總結
simply-lazy 中雖然只是實現(xiàn)了 Lazy.js 的三個惰性計算方法（map，filter、take），但從中已經(jīng)可以看出 Lazy.js 的設計模式了。不同的計算方法體現(xiàn)的是不同的計算模式，而這計算模式則是通過不同的 Sequence 類型來實現(xiàn)的。
具體的 Sequence 類型包含了特定的計算模式，這從其類型名稱上也能看出來。例如，MappedArrayWrapper、MappedSequence、IndexedMappedSequence 都是對應 map 計算模式。
而求值的過程，或者說求值的模式是統(tǒng)一的，都是借助 Sequence 鏈，鏈條上的每個 Sequence 節(jié)點只負責：
- 上傳：向上級 Sequence 獲取值
- 下達：向下級 Sequence 傳遞至
- 求值：應用類型對應的計算模式對數(shù)據(jù)進行計算或者過濾等操作
由內嵌了不同的計算模式的 Sequence 構成的鏈，就實現(xiàn)了惰性求值。
當然，這只是 Lazy.js 中的惰性求值的實現(xiàn)，并不意外這“惰性求值”就等于這里的實現(xiàn)，或者說惰性求值的全部特性就是這里 Lazy.js 的全部特性。更何況，本文主要分析的 simply-lazy 也只是從模式上對 Lazy.js 的惰性求值進行了說明，也并不包含 Lazy.js 的全部特性（例如生成無限長度的列表）。
不管怎樣，還是閱讀過后能夠給你帶來一點有價值的東西。哪怕只有一點，我也很高興。
文中對 Lazy.js 的惰性求值的分析僅是我個人的見解，如果錯漏，歡迎指正！
本文版權歸黑馬程序員web前端開發(fā)學院所有，歡迎轉載，轉載請注明作者出處，謝謝！
作者：黑馬程序員web前端培訓學院；
首發(fā)：http://ko1818.cn/news/web.html
JavaEE
鴻蒙應用開發(fā)
集成電路應用開發(fā)
人工智能開發(fā)
AI+Linux云計算運維
Python+大數(shù)據(jù)開發(fā)
AI+設計
軟件測試
新媒體+短視頻
HTML&JS+前端
據(jù)學科列表頁右側.png)
.jpg)