[Day17] Clojure Laziness (1) Lazy evaluation

早安！

大家一定都有聽過：懶惰是工程師的美德:)

來放一張美女貓貓Cara的沙龍照

懶惰的工程師～當然要發明懶惰的工具！

但在發明懶惰工具的時，首先需要work hard to be lazy

因此趁著假日早晨，心情上比較放鬆的時光

來研究一個自己覺得最不好理解的主題

咚咚隆咚將將將～那就是...

"Lazy evaluation"

Lazy evaluation (懶惰求值、惰性求值、惰性計算)

實作lazyiness的特點就是需要時才call (call-by-need)

還有聽過摸魚求值的翻譯 XD

好處是：

• 讓電腦要做的工作最小化
• 空間複雜度上(Space Complexity)可以做到極大的優化

和惰性求值相反的是 及早求值

Eager evaluation / Greedy evaluation (及早求值、熱切求值、貪婪求值)

大部分的傳統程式語言求值的策略是Eager evaluation (及早求值) call-by-value

那實作lazyiness有什麼好處呢？主要有兩個

• 節省內存空間
• 提高執行速度

Why eager evaluation 節省內存空間?

來用以下算式為例，很多語言的表達式(例如：Ruby)都是這樣寫的：

num = 1 + 2 * (3 * 4 / 2)

=> 13

由於表達式(expression) 1 + 2 * (3 * 4 / 2) 會占比較多空間，
因此當num被賦值為13之後，表達式所占用的空間就可以立即釋放掉囉！

Why 提高執行速度?

當以後call到num時， num這個數值就可以直接用於運算，而不是call 1 + 2 * (3 * 4 / 2) 減少一次計算過程，提高執行效率

複雜度complexity: 時間複雜度 vs 空間複雜度

既然貪婪（求值）很好，那為什麼要懶惰呢？ :P

有滿滿乾糧但還是貪婪搶罐罐的貓貓們

因為...我們關心的是當電腦處理大量資料時，演算法是否夠好

用javascript舉一個槽狀迴圈的例子來看，
所有的code跑完之後，運算式會被執行幾次：

function multiplyElement(arr) {

  int num;   // 在記憶體上宣告變數，不需執行
  num = 1    // 執行 1 次: 數值 1 assign 給變數num 作為起始值

  //執行 n+1 次: 從 i=0 累加到 i=n（假設陣列長度為n)
  for (let i = 0; i < arr.length; i++) {
  
     //因為在第二層迴圈，執行 n* (n+1) 次: 從 i=0 累加到 i=n（假設陣列長度為n)，
    for (let j = 0; j < arr[i].length; j++) {
    
      // 執行 n^2次:  (for i)的 n 次 * (for j) 的 n 次。
      num *= arr[i][j];
    }
  }
  return num;
}

multiplyElement([[1, 2],[3, 4], [5, 6]]);
=> 720

multiplyElement([[5, 6, 7, 8]]);
=> 1680

照著註解的算法，function multiplyElement(arr)執行了

1+(n+1)+n*(n+1)+n^2 = 2n^2 + 2n + 1 次的指令

如果以call by value的策略，
當數值設定為一個很大的數時候，
例如我放了元素個數(arr.length)為一萬個的array
執行的算式也變得超。多。次！！

irb(main):008:0> 2* (n*n) + 2*n + 1
=> 200020001

一下子資產就暴增就好幾個億呀

這是一種立馬暴斃增的fu...

時間複雜度 Time Complexity

上面的例子程式執行的次數，

1+(n+1)+n*(n+1)+n^2 = 2n^2 + 2n + 1

通常當數字大到一定程度時，
我們只看最高次方項（n的平方），
並且忽略掉項次前的係數(2)，後面也可以忽略，簡稱 BigO (最大的O(?))

因此舉例中的BigO是O(n²)

常見演算法分類與時間複雜度

在這裏列出常見的時間複雜度與演算法的Big O

• O(1)：(array / vector)讀取

• O(n)：一層for loop/ 簡易搜尋

• O(n²)： 雙層nested for loop(就是剛剛的例子！) / 選擇排序法、插入排序法

• O(log n)：二分搜尋

• O(n logn)：快速排序 / 合併排序

• O(2^n)：費波那契數列 (Fibonacci)

從網路上找到畫出時間複雜度的排序給大家參考 :

因為本系列文主題是講Clojure Functional programming，而非搜尋或演算法，
細節就讓有興趣的看倌自行查訊：）

空間複雜度 Space Complexity

電腦執行演算法所需要耗費的記憶體空間成本，就是所謂的Space Complexity

一寸光陰一寸金，時間分秒必爭，
現在的電腦效能越來越好，所以為什麼不用空間換取時間呢？

Space Complexity和 Time Complexity通常可以互相權衡，跟人生一樣(?)
於是 Lazy evaluation就出現啦！

淺談Lazy Ealuation

在使用延遲求值的時候，
表達式會在該值被取用的時候才求值，而非被綁定到變量之後就馬上立即求值。

有些程式語言如Haskell，其預設就是進行惰性求值，
因此在找lazyness資料的時候超級常搜尋到相關例子。

以下這兩篇都是談haskell的，但蠻值得一讀：

• Why is lazy evaluation useful?
• Lazy Evaluation and Time Complexity

Clojure的Laziness懶惰是懶在哪裡?

Clojure大部分實作是eagerly evaluated(熱切求值)的，
那它的lazy evaluation是出現在哪裡呢?

答案是 Lazy sequences!

Clojure has the ability to treat any data structure conforming to the sequence interface as a lazy sequence Ref

我們可以把Lazy sequences 當作是對sequences序列做出抽象化，不需要管這個 sequences從哪裡來、多少element在裡面、裡面的element是哪種data structure...等。

再加上call-by-needed的概念，雖然我們還不知道裡面放什麼東西，值是多少，但只要想用的時候就可以得到它(的值)。

（怎麼有這麼好的事?!）

在clojure裡我們對Lazy sequences還不知道的時候，

叫它 unrealized element，
知道的話叫做realized

例如：

我們發現Flow control分類裡的API有個分類叫做 Laziness

在懶貓lazy-cat 底下有個 doall，

之前在介紹flow controll時有介紹過，但當時還一知半解。

其實呀～doall用途，就是強制去 realize lazy sequence

前輩舉了一個很好的例子：

(realized? (map identity [1 2 3]))
=>false

(realized? (doall (map identity [1 2 3])))
=>true

有沒有發現 doall realized?後會變成true（證明它是for lazy sequence用的啦！）

懶貓OS: 要不要來 realized? 了解我一下呀 ^_< 啾咪

Clojure Lazy Sequence API

以下這些分類都是Lazy Sequence，包括我們最常用的 map 和 filter

map
filter
range
remove

take
take-while

drop
drop-while

在以下⬇️我們很常舉的例子（求取50以內的偶數平方和）裡，

包括 filter、map、filter，都是用來實現lazy sequences，
值並不會馬上被運算出來，
所以才能將這些好用的functions一串接著一串串起來，
一直到sequence is realized（在我們的例子是 reduce）

(->> (range 50)
     (filter even?)
     (map (fn [x] (* x x)))
     (reduce +))

Lazy language還有一個好處，就是可以幫助我們安心地使用運算式，
而不用擔心值會突然在某個地方被改掉，避免side-effect
（side-effect 也是未來有機會會想聊的主題）

下回預告: 遞迴: 以費波那契數列 (Fibonacci)為例

前面有提及費波那契數列 (Fibonacci)是 O(2^n)，
時間複雜度也是超級快速遞增的（只比 n^3和n!好一點）

今天先聊到這裡，先去當一隻懶貓貓（不想努力了）

明天來用 lazy-seq做出費波那契 (Fibonacci)數列吧！

附錄: 一堆Lazy Sequence API系列 (節錄)

Reference: https://clojuredocs.org/quickref

有了Lazy概念之後，是不是又對這些以前文章裡有介紹過API，有更進一步的體會與認識呢？；）