作者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/cn.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