iT邦幫忙

1

SICP lec6a : 流 I part3 (lazy seq 解釋)

此篇為 SICP教程 6a 的筆記

找出 1,000 ~ 1,000,000 中的第二個質數

若是 的方式來處理,流程如下:

  1. map 所有 1,000 ~ 1,000,000 的數字
  2. filter 其中的質數

這顯然是非常非常佔記憶體的事情,若是更大的範圍呢,況且只是要找第二個數,用這個例子來比較傳統 時序 概念與概念誰比較適合的話,答案反而是前者。

現在反而矛盾了,之前把 吹捧得這麼厲害,能把邏輯複雜的規則呈現的簡單又清楚,但實務上卻是佔記憶體且無法處理大型數據,怎麼會這樣?

其實接下來才是真正厲害的地方。

之所以會輸 傳統時序 的地方,就是需要 先產生所有計算要用到的數據 才進行處理,那能不能讓數據在 需要計算 的時候再進行計算呢?

如果用圖形來表示(影片當中用道具):
失敗的流:
https://ithelp.ithome.com.tw/upload/images/20190525/201175164t34oneAtp.png
https://ithelp.ithome.com.tw/upload/images/20190525/20117516LGEfYCGeDt.png
https://ithelp.ithome.com.tw/upload/images/20190525/20117516lYGGLtYbaX.png
https://ithelp.ithome.com.tw/upload/images/20190525/2011751679HzNI1gAd.png

想像中成功的流:
https://ithelp.ithome.com.tw/upload/images/20190525/20117516I6SntLuziu.png
當result要求一個數據,就從 的尾部(tail)向最後一個process拉取一個數據,最後一個process再向前一個process拉取,以此類推。只有在末端要求一定量數據時,源頭才產生定量的數據。

但有什麼 data structure 可以這樣搞? 有的! 而且是最基本的種類,就是 "function as data" 來達成這個夢幻的

首先認識幾個基本元素 con-stream, head, tail

(defn con-stream [x y]
    (cons x (delay y)))
(defn head [s] (car s))
(defn tail [s] (force (cdr s)))
  • delay 所做的有兩件事 1. 產生function的表達式 2.一個執行許可,當接收到執行許可時再去執行。
  • force 就是 delay 的執行許可

https://ithelp.ithome.com.tw/upload/images/20190525/20117516iNw5AjOhcA.png

回到最一開始的問題,來檢視一下 夢幻流 的執行過程

(head (tail (filter prime? (map 每一個數 1000 1000000)))))

(map 每一個數 1000 1000000) -> (cons 1000 (delay (map 每一個數 1001 1000000)))

  • map第一個數 1000 出來計算
  • 其他的先不計算
(filter prime? (map 每一個數 1000 1000000))
-> (filter prime? 1000)
-> (filter prime?(tail (cons 1000 (delay (map 每一個數 1001 1000000)))))
  • filter prime? 計算第一個數 1000
  • 執行tail,force (map 每一個數 1001 1000000)
  • 遞迴的對 tail 做 filter prime?
  • 產生第一個質數後停止,但要求是第二個因此繼續啟動

上述可見,filter出來的數據,不會比map的還要多,因為filter去要求(force delay)的時候,數據才會產生。

真正神奇的地方 delayforce ,實作上也非常的簡單

(defn delay [exp] (fn [] (exp)))
(defn force [fn] (fn))

delay 神奇的地方在於將 "預期事件的執行順序" 與 "實際電腦的執行順序" 解耦開來,以至於可以用 "綜觀全局不考慮每個時間狀態" 的表示方式,做出 "最有效率,不佔無效空間" 的執行。

還有一個問題,當執行遞迴的tail時會出現 (tail (tail (tail...))),每一次計算新的數據,就要把以前的tail都計算一次,相當沒有效率,因此若能將之前計算過的tail都記錄下來就能避免,因此將delay改成為

(defn delay [exp] (memo-proc (fn [] (exp))))

memo-proc是一個function,記錄前面所有產生過的數據,讓每一次force tail時只做一次的計算。


尚未有邦友留言

立即登入留言