惰性求值——lodash源碼解讀

前言

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 惰性求值做法

普通的做法存在一個問題：每個方法各做各的事，沒有協調起來浪費了很多資源。
如果能先把要做的事，用小本本記下來