前言

lodash受歡迎的一個(gè)原因，是其優(yōu)異的計(jì)算性能。而其性能能有這么突出的表現(xiàn)，很大部分就來(lái)源于其使用的算法——惰性求值。
本文將講述lodash源碼中，惰性求值的原理和實(shí)現(xiàn)。

一、惰性求值的原理分析

惰性求值（Lazy Evaluation），又譯為惰性計(jì)算、懶惰求值，也稱為傳需求調(diào)用（call-by-need），是計(jì)算機(jī)編程中的一個(gè)概念，它的目的是要最小化計(jì)算機(jī)要做的工作。
惰性求值中的參數(shù)直到需要時(shí)才會(huì)進(jìn)行計(jì)算。這種程序?qū)嶋H上是從末尾開始反向執(zhí)行的。它會(huì)判斷自己需要返回什么，并繼續(xù)向后執(zhí)行來(lái)確定要這樣做需要哪些值。

以下是How to Speed Up Lo-Dash ×100? Introducing Lazy Evaluation.（如何提升Lo-Dash百倍算力？惰性計(jì)算的簡(jiǎn)介）文中的示例，形象地展示惰性求值。

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();

程序的目的，是對(duì)數(shù)據(jù)集gems進(jìn)行篩選，選出3個(gè)price小于10的數(shù)據(jù)。

1.1 一般的做法

如果拋開lodash這個(gè)工具庫(kù)，讓你用普通的方式實(shí)現(xiàn)var chosen = _(gems).filter(priceLt(10)).take(3);那么，可以用以下方式：
_(gems)拿到數(shù)據(jù)集，緩存起來(lái)。
再執(zhí)行filter方法，遍歷gems數(shù)組（長(zhǎng)度為10），取出符合條件的數(shù)據(jù)：

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

然后，執(zhí)行take方法，提取前3個(gè)數(shù)據(jù)。

[{ name: 'Sunstone', price: 4 },{ name: 'Sugilite', price: 7 },{ name: 'Diopside', price: 3 } ]

總共遍歷的次數(shù)為：10+3。
執(zhí)行的示例圖如下：

1.2 惰性求值做法

普通的做法存在一個(gè)問(wèn)題：每個(gè)方法各做各的事，沒(méi)有協(xié)調(diào)起來(lái)浪費(fèi)了很多資源。
如果能先把要做的事，用小本本記下來(lái)?，然后等到真正要出數(shù)據(jù)時(shí)，再用最少的次數(shù)達(dá)到目的，豈不是更好。
惰性計(jì)算就是這么做的。
以下是實(shí)現(xiàn)的思路：

• _(gems)拿到數(shù)據(jù)集，緩存起來(lái)
• 遇到filter方法，先記下來(lái)
• 遇到take方法，先記下來(lái)
• 遇到value方法，說(shuō)明時(shí)機(jī)到了
• 把小本本拿出來(lái)，看下要求：要取出3個(gè)數(shù)，price<10
• 使用filter方法里的判斷方法priceLt對(duì)數(shù)據(jù)進(jìn)行逐個(gè)裁決

[{ name: 'Sunstone', price: 4 }, => priceLt裁決 => 符合要求，通過(guò) => 拿到1個(gè){ name: 'Amethyst', price: 15 }, => priceLt裁決 => 不符合要求{ name: 'Prehnite', price: 20}, => priceLt裁決 => 不符合要求{ name: 'Sugilite', price: 7 }, => priceLt裁決 => 符合要求，通過(guò) => 拿到2個(gè){ name: 'Diopside', price: 3 }, => priceLt裁決 => 符合要求，通過(guò) => 拿到3個(gè) => 夠了，收工！{ name: 'Feldspar', price: 13 },{ name: 'Dioptase', price: 2 },{ name: 'Sapphire', price: 20 } ]

如上所示，一共只執(zhí)行了5次，就把結(jié)果拿到。
執(zhí)行的示例圖如下：

1.3 小結(jié)

從上面的例子可以得到惰性計(jì)算的特點(diǎn)：

• 延遲計(jì)算，把要做的計(jì)算先緩存，不執(zhí)行
• 數(shù)據(jù)管道，逐個(gè)數(shù)據(jù)通過(guò)“裁決”方法，在這個(gè)類似安檢的過(guò)程中，進(jìn)行過(guò)關(guān)的操作，最后只留下符合要求的數(shù)據(jù)
• 觸發(fā)時(shí)機(jī)，方法緩存，那么就需要一個(gè)方法來(lái)觸發(fā)執(zhí)行。lodash就是使用value方法，通知真正開始計(jì)算

二、惰性求值的實(shí)現(xiàn)

依據(jù)上述的特點(diǎn)，我將lodash的惰性求值實(shí)現(xiàn)進(jìn)行抽離為以下幾個(gè)部分：

2.1 實(shí)現(xiàn)延遲計(jì)算的緩存

實(shí)現(xiàn)_(gems)。我這里為了語(yǔ)義明確，采用lazy(gems)代替。

var MAX_ARRAY_LENGTH = 4294967295; // 最大的數(shù)組長(zhǎng)度// 緩存數(shù)據(jù)結(jié)構(gòu)體 function LazyWrapper(value){this.__wrapped__ = value;this.__iteratees__ = [];this.__takeCount__ = MAX_ARRAY_LENGTH; }// 惰性求值的入口 function lazy(value){return new LazyWrapper(value); }

• this.__wrapped__ 緩存數(shù)據(jù)
• this.__iteratees__ 緩存數(shù)據(jù)管道中進(jìn)行“裁決”的方法
• this.__takeCount__ 記錄需要拿的符合要求的數(shù)據(jù)集個(gè)數(shù)

這樣，一個(gè)基本的結(jié)構(gòu)就完成了。

2.2 實(shí)現(xiàn)filter方法

var LAZY_FILTER_FLAG = 1; // filter方法的標(biāo)記// 根據(jù) 篩選方法iteratee 篩選數(shù)據(jù) function filter(iteratee){this.__iteratees__.push({'iteratee': iteratee,'type': LAZY_FILTER_FLAG});return this; }// 綁定方法到原型鏈上 LazyWrapper.prototype.filter = filter;

filter方法，將裁決方法iteratee緩存起來(lái)。這里有一個(gè)重要的點(diǎn)，就是需要記錄iteratee的類型type。
因?yàn)樵趌odash中,還有map等篩選數(shù)據(jù)的方法，也是會(huì)傳入一個(gè)裁決方法iteratee。由于filter方法和map方法篩選方式不同，所以要用type進(jìn)行標(biāo)記。
這里還有一個(gè)技巧：

(function(){// 私有方法function filter(iteratee){/* code */}// 綁定方法到原型鏈上LazyWrapper.prototype.filter = filter; })();

原型上的方法，先用普通的函數(shù)聲明，然后再綁定到原型上。如果工具內(nèi)部需要使用filter，則使用聲明好的私有方法。
這樣的好處是，外部如果改變LazyWrapper.prototype.filter，對(duì)工具內(nèi)部，是沒(méi)有任何影響的。

2.3 實(shí)現(xiàn)take方法

// 截取n個(gè)數(shù)據(jù) function take(n){this.__takeCount__ = n;return this; };LazyWrapper.prototype.take = take;

2.4 實(shí)現(xiàn)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 = [];// 標(biāo)簽語(yǔ)句outer:while(length-- && resIndex < takeCount){// 外層循環(huán)待處理的數(shù)組index += dir;var iterIndex = -1;var value = array[index];while(++iterIndex <　iterLength){// 內(nèi)層循環(huán)處理鏈上的方法var data = iteratees[iterIndex];var iteratee = data.iteratee;var type = data.type;var computed = iteratee(value);// 處理數(shù)據(jù)不符合要求的情況if(!computed){if(type == LAZY_FILTER_FLAG){continue outer;}else{break outer;}}}// 經(jīng)過(guò)內(nèi)層循環(huán)，符合要求的數(shù)據(jù)result[resIndex++] = value;}return result; }LazyWrapper.prototype.value = lazyValue;

這里的一個(gè)重點(diǎn)就是：標(biāo)簽語(yǔ)句

outer:while(length-- && resIndex < takeCount){// 外層循環(huán)待處理的數(shù)組index += dir;var iterIndex = -1;var value = array[index];while(++iterIndex <　iterLength){// 內(nèi)層循環(huán)處理鏈上的方法var data = iteratees[iterIndex];var iteratee = data.iteratee;var type = data.type;var computed = iteratee(value);// 處理數(shù)據(jù)不符合要求的情況if(!computed){if(type == LAZY_FILTER_FLAG){continue outer;}else{break outer;}}}// 經(jīng)過(guò)內(nèi)層循環(huán)，符合要求的數(shù)據(jù)result[resIndex++] = value;}

當(dāng)前方法的數(shù)據(jù)管道實(shí)現(xiàn)，其實(shí)就是內(nèi)層的while循環(huán)。通過(guò)取出緩存在iteratees中的裁決方法取出，對(duì)當(dāng)前數(shù)據(jù)value進(jìn)行裁決。
如果裁決結(jié)果是不符合，也即為false。那么這個(gè)時(shí)候，就沒(méi)必要用后續(xù)的裁決方法進(jìn)行判斷了。而是應(yīng)該跳出當(dāng)前循環(huán)。
而如果用break跳出內(nèi)層循環(huán)后，外層循環(huán)中的result[resIndex++] = value;還是會(huì)被執(zhí)行，這是我們不希望看到的。
應(yīng)該一次性跳出內(nèi)外兩層循環(huán)，并且繼續(xù)外層循環(huán)，才是正確的。
標(biāo)簽語(yǔ)句，剛好可以滿足這個(gè)要求。

2.5 小檢測(cè)

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// 得到結(jié)果： [1, 2]

2.6 小結(jié)

整個(gè)惰性求值的實(shí)現(xiàn)，重點(diǎn)還是在數(shù)據(jù)管道這塊。以及，標(biāo)簽語(yǔ)句在這里的妙用。其實(shí)實(shí)現(xiàn)的方式，不只當(dāng)前這種。但是，要點(diǎn)還是前面講到的三個(gè)。掌握精髓，變通就很容易了。

結(jié)語(yǔ)

惰性求值，是我在閱讀lodash源碼中，發(fā)現(xiàn)的最大閃光點(diǎn)。
當(dāng)初對(duì)惰性求值不甚理解，想看下javascript的實(shí)現(xiàn)，但網(wǎng)上也只找到上文提到的一篇文獻(xiàn)。
那剩下的選擇，就是對(duì)lodash進(jìn)行剖離分析。也因?yàn)檫@，才有本文的誕生。
希望這篇文章能對(duì)你有所幫助。如果可以的話，給個(gè)star :)

最后，附上本文實(shí)現(xiàn)的簡(jiǎn)易版lazy.js完整源碼：
https://github.com/wall-wxk/blogDemo/blob/master/lodash/lazy.js

---

喜歡我文章的朋友，可以通過(guò)以下方式關(guān)注我：

• 「star」 或 「watch」 我的GitHub blog
• RSS訂閱我的個(gè)人博客：王先生的基地

總結(jié)

以上是生活随笔為你收集整理的惰性求值——lodash源码解读的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。