作者CindyLinz (Cindy Wang)
看板PLT
標題[情報] Functional Thursday #35
時間Thu Jan 28 15:21:44 2016
http://www.meetup.com/Functional-Thursday/events/228168270/
時間: 2016.2.4 (四) 晚上 19:30
地點: Mozilla Space
主題: Pure Functional Real-time Queue
講者: CindyLinz
在 pure functional 的世界裡, 如果只使用 immutable 的資料操作.
用 list (就是 [a]) 來實作 stack 是很容易的, 但要實作 queue 就相對複雜一點..
而如果要實作每一步操作都只需要 O(1) 時間的 queue, 就更需要一些技巧了.
(註: 在號稱 pure functional 的 Haskell 裡面,
用到的資料結構不一定都是 pure functional data structure 喔)
這一次介紹用的程式語言是 Haskell.
從一個簡單的 amortized O(1) 的 queue 實作開始,
再逐步把它改成 worst case O(1) 的 queue.
其中會介紹一個叫作 schedule 的技巧,
可以把任意的 amortized 演算法改成 real time 演算法.
(也會稍微介紹一下 time complexity, 以及什麼叫 amortized,
什麼叫 worst case/real time 的 time complexity.)
最後我們會獲得一個 pure functional 的 real-time queue.
它的每一步操作只需要 O(1) 的時間, 而且可以隨意把任意的歷史記錄留下來,
各自發展自己的新歷史, 而且不管怎樣翻來覆去地用,
每一個操作都只需要 O(1) 的時間.
我覺得這個資料結構本身... 不見得能有多實用 XD
但是實作過程中所用到的 schedule 技巧, 倒是非常值得一看!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.78.5
※ 文章網址: https://webptt.com/m.aspx?n=bbs/PLT/M.1453965707.A.105.html
1F：推 appleway: 有沒有錄影之類的，每次都想參加但是人在 01/28 15:53
2F：→ appleway: 國外 01/28 15:53
3F：→ CindyLinz: 我我我..考慮考慮 <囧> 01/28 23:00
4F：推 FRAXIS: 這技巧可以用在 deque 上嗎？ 01/29 00:03
5F：→ CindyLinz: 理論上應該可以. 應該會更複雜些.. 01/29 02:35
6F：推 FRAXIS: 我想知道你中間會用到幾條 list? 依賴 lazy-evaluation? 01/29 09:08
7F：→ FRAXIS: 因為這問題我常常看到 好像會需要 6 個 list 才能辦到 01/29 09:08
8F：→ CindyLinz: 那就不知道了~ 因為我沒實際作過 deque ^^| 01/29 11:53
9F：推 FRAXIS: 喔 我其實想問 queue 需要幾條 list 幫忙 才能O(1) 01/29 19:02
10F：推 suhorng: 把 amortized 變成 real time 好猛@@ 聽起來好威 01/29 21:01
11F：推 emind: 國外+1 想參加 01/30 03:35
12F：→ xcycl: 在 Okasaki 書中學到的嗎？ 01/30 06:53