[Day03] Lazy Evaluation


lazy evaluation 一般翻成 惰性求值,顧名思義他就是很懶惰的求值(誤)。
 
lazy evaluation 的意義在於當我們真的需要用到值的時候才去求值,而要達成這樣的效果需要滿足一些大前提。
 
讓我們直接從原生的 JavaScript,跟模仿 FP 風格的 Immutable.js的一個範例做比較,直接比較看看 lazy evaluation 跟非 FP 的 eager evaluation 的差別:
Vainilla JS

Array(1000000).fill(0).map((_, index) => index + 1)
  .filter((n, index) => index >= 1000)
  .map(n => -n)
  .filter(n => n % 2 === 0)
  .filter((n, index) => index < 2)
  .reduce((r, n) => r * n, 1)

Immutable.js

Immutable.Range(1, 1000000)
  .skip(1000)
  .map(n => -n)
  .filter(n => n % 2 === 0)
  .take(2)
  .reduce((r, n) => r * n, 1)

以上這兩段程式碼,語意上應該是等價的:產生一個 1~1000000 的陣列 => 不拿前 1000 個 => 把剩下的數字都乘以 -1 => 取剩下數字裡的偶數 => 拿前兩個數 => 用 reduce 得到這兩個數的乘積。
 
那他們實際運行上的差別在哪呢?
 
差別在於,原生 JS 版本的 code 在第一行,真的會產生一個有 1000000 個元素的陣列,並且在 filter、 map 、 reduce 的過程,都會遍歷一次這個陣列。也就是說僅管最後這一段程式碼僅產生一個元素,這段程式碼卻會對 1000000 個元素通通都做一次運算!而用了 lazy evaluation 的 Immutable.js ,並不會真的產生一個陣列,僅只有在真的需要計算值的時候才會開始計算。
 
不妨這樣想像:今天老闆說要拜訪客戶 A,一小時後又交代要拜訪客戶 B,再一小時後又請你去採購 C 物品,而三件事的期限都是隔天下午五點前。

  1. eager evaluation 的員工:在老闆交代要拜訪 A 客戶時馬上就出門,回來之後聽到老闆要拜訪 B 客戶又馬上再出門,回來聽到要採購 C 物品時,又匆匆的再出發。
  2. lazy evaluation 的員工:老闆叫我做明天五點前完成 A,我先記著,不急;老闆又叫我明天五點前完成 B,我一樣記著,還不急;老闆又叫我明天五點前做 C ,連採購也要交給我,偷偷抱怨數十句,一樣先記在我的筆記本。等到隔天的下午三點,出門一趟把三件事情一起解決,完美地在五點前達成要求。  

由這兩種情況可見, eager evaluation 很可能過早處理計算,導致增加很多不必要的開銷(多跑兩趟),而 lazy evaluation 在同樣的時限做了一樣的事情,還省了不少來回跑的成本,正所謂懶惰是工程師的美德呢。
 
但是如第一段所講的,惰性求值有一個大前提:不會改動原本的陣列的元素(或著說:沒有副作用)。試想如果在範例程式碼中的任何一段操作,改動了原本的陣列,讓這個原陣列從 1000000 個元素變成 999999 個元素,則結果很可能就會變得不一樣了。這也是為什麼 Day01 中提到 FP 的 immutable 特性,我們僅能透過一連串沒有副作用純函數去從原本的陣列衍生出新的一組陣列,而透過把這些函數組合起來並記下來,就可以只用必要的元素作計算得到結果。
 
假設你已經了解 lazy evaluation 的話,就會發現用 Immutable.js 的版本,將 range 改成 Infinity 也不會有任何問題。

Immutable.Range(1, Infinity)
  .skip(1000)
  .map(n => -n)
  .filter(n => n % 2 === 0)
  .take(2)
  .reduce((r, n) => r * n, 1)

能夠處理無限大的陣列或 Stream 等等所謂的 List-like 結構,就是建立在 immutable + lazy evaluation 的前提之下。最近流行的 reactive programming ,就是把事件的觸發順序抽象成流(stream),也就是類似一個無限大、會一直新增東西進來的陣列,然後透過 map/reduce/filter 等等方法,搭配 lazy evaluation,就可以用很 Functional 的方法優雅的處理複雜的事件觸發。

參考:
Immutable.js 簡介
Immutability 及 Lazy evaluation

#Functional Programming #程式設計
Functional Programming 到底是什麼?為什麼最近這麼夯? 這一系列的文章會探討幾個 FP 的特性,讓大家一起體驗 FP 的魔力。






Related Posts

Nginx + Flask 動態與靜態頁面分離入門教學

Nginx + Flask 動態與靜態頁面分離入門教學

在 Ethereum 上開發簡單的 Todo App

在 Ethereum 上開發簡單的 Todo App

python筆記(3)

python筆記(3)

Day06 從案例看原生 History API (中)

Day06 從案例看原生 History API (中)

TechBridge 技術週刊編輯第 200 期的感性時間

TechBridge 技術週刊編輯第 200 期的感性時間

TCP/IP 四層模型/ HTTP 相關筆記

TCP/IP 四層模型/ HTTP 相關筆記



Comments