作者CindyLinz (Cindy Wang)
看板PLT
標題Re: [情報] Functional Thursday #35
時間Sat Jan 30 16:12:12 2016
※ 引述《CindyLinz (Cindy Wang)》之銘言：
: --
:
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.78.5
: ※ 文章網址: https://webptt.com/m.aspx?n=bbs/PLT/M.1453965707.A.105.html
: 推 appleway: 有沒有錄影之類的，每次都想參加但是人在 01/28 15:53
: → appleway: 國外 01/28 15:53
: → CindyLinz: 我我我..考慮考慮 <囧> 01/28 23:00
: 推 FRAXIS: 這技巧可以用在 deque 上嗎？ 01/29 00:03
: → CindyLinz: 理論上應該可以. 應該會更複雜些.. 01/29 02:35
: 推 FRAXIS: 我想知道你中間會用到幾條 list? 依賴 lazy-evaluation? 01/29 09:08
: → FRAXIS: 因為這問題我常常看到 好像會需要 6 個 list 才能辦到 01/29 09:08
: → CindyLinz: 那就不知道了~ 因為我沒實際作過 deque ^^| 01/29 11:53
: 推 FRAXIS: 喔 我其實想問 queue 需要幾條 list 幫忙 才能O(1) 01/29 19:02
我看了一下程式碼, 我的寫法總共有用到 6 個 list
不過.. 是這樣子的 6 個:
[a] ([a] [a] | [a] [a] [a])
同一時間會有 3 或 4 個, 不是同時有 6 個.
: 推 suhorng: 把 amortized 變成 real time 好猛@@ 聽起來好威 01/29 21:01
: 推 emind: 國外+1 想參加 01/30 03:35
: → xcycl: 在 Okasaki 書中學到的嗎？ 01/30 06:53
對. 「schedule」就是他書中用的詞, 也許就是他發明的..
(書名 Purely Functional Data Structures)
不過他書中的例子寫一半, 另一半是用大量的文字話唬爛的..
(好像是類似這樣, 以前讀的時候的印象,
雖然也有可能是我那時沒看懂wwww
不過他那本書真的在舉例的時候會把難寫的部分跳過不寫,
例如說他舉例二元平衡搜尋樹, 寫了插入與查詢的部分,
然後就說刪除的部分也很簡單請讀者自行練習..
((最好是刪除很簡單啦.... 刪除是最難寫的好嗎wwww
光是刪除的 code 就比其他全部加起來還多吧wwww)))
總之, 我這次是應用他的想法, 重新作一個(練習一個)完整例子就是了~
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.78.5
※ 文章網址: https://webptt.com/m.aspx?n=bbs/PLT/M.1454141534.A.3B2.html
1F：推 c225: 因為是lazy 所以amortized的東東才會變real time嗎？ 01/30 16:49
2F：推 FRAXIS: 我會這樣問 是因為我看到莊庭瑞老師的論文上面有寫 01/30 18:49
3F：→ FRAXIS: 說如果沒有 lazy evaluation 的話需要 6 個 list 01/30 18:49
4F：→ FRAXIS: 不過那已經是 93 年的 論文了 想知道最近有沒有突破 01/30 18:51
5F：推 FRAXIS: 說錯了.. 論文上沒寫有幾個 list 但是網路上有人說要 6 個 01/30 18:54
7F：→ FRAXIS: 論文上是寫怎樣作 real-time 的 deque 01/30 18:55
8F：→ CindyLinz: 嗯我是用 lazy eval 的 Haskell, 寫 queue 不是 deque 01/30 20:00
9F：→ CindyLinz: 然後, 我沒有去想怎麼省 list 個數, 所以如果不是最佳 01/30 20:01
10F：→ CindyLinz: 解, 應該是正常的 (? XD 01/30 20:01
11F：→ CindyLinz: 不過.... list 的個數很重要嗎? 不考慮各 list的長度嗎 01/30 20:02
12F：推 FRAXIS: 我想全部 list 長度總和就是原本 queue 裡面的元素個數吧 01/30 20:11
13F：→ CindyLinz: 那既然長度總和一樣, 那為什麼需要在意 list 個數呢? 01/31 01:53
14F：推 FRAXIS: 理論上看是沒什麼差別 反正都是 real-time 01/31 02:24
15F：推 FRAXIS: 只是想知道有沒有比較好的實作方式而已 01/31 02:26
16F：推 dryman: 看到刪除自己做的時候我也是覺得很想罵髒話XD 02/15 14:08
17F：推 scwg: 那本書是人家的博士論文啊... 刻論文的時候當然太麻煩的跳過 02/23 10:57
18F：推 suhorng: 印象裡博士論文跟後來出的書好像有點差? 有重新整理過 02/23 16:32