Re: [情報] Functional Thursday #35

看板PLT (程式語言與理論)作者 (Cindy Wang)時間8年前 (2016/01/30 16:12), 編輯推噓9(909)
留言18則, 6人參與, 最新討論串2/2 (看更多)
※ 引述《CindyLinz (Cindy Wang)》之銘言: : -- : ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 112.121.78.5 : ※ 文章網址: https://www.ptt.cc/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://www.ptt.cc/bbs/PLT/M.1454141534.A.3B2.html

01/30 16:49, , 1F
因為是lazy 所以amortized的東東才會變real time嗎?
01/30 16:49, 1F

01/30 18:49, , 2F
我會這樣問 是因為我看到莊庭瑞老師的論文上面有寫
01/30 18:49, 2F

01/30 18:49, , 3F
說如果沒有 lazy evaluation 的話需要 6 個 list
01/30 18:49, 3F

01/30 18:51, , 4F
不過那已經是 93 年的 論文了 想知道最近有沒有突破
01/30 18:51, 4F

01/30 18:54, , 5F
說錯了.. 論文上沒寫有幾個 list 但是網路上有人說要 6 個
01/30 18:54, 5F

01/30 18:55, , 6F

01/30 18:55, , 7F
論文上是寫怎樣作 real-time 的 deque
01/30 18:55, 7F

01/30 20:00, , 8F
嗯我是用 lazy eval 的 Haskell, 寫 queue 不是 deque
01/30 20:00, 8F

01/30 20:01, , 9F
然後, 我沒有去想怎麼省 list 個數, 所以如果不是最佳
01/30 20:01, 9F

01/30 20:01, , 10F
解, 應該是正常的 (? XD
01/30 20:01, 10F

01/30 20:02, , 11F
不過.... list 的個數很重要嗎? 不考慮各 list的長度嗎
01/30 20:02, 11F

01/30 20:11, , 12F
我想全部 list 長度總和就是原本 queue 裡面的元素個數吧
01/30 20:11, 12F

01/31 01:53, , 13F
那既然長度總和一樣, 那為什麼需要在意 list 個數呢?
01/31 01:53, 13F

01/31 02:24, , 14F
理論上看是沒什麼差別 反正都是 real-time
01/31 02:24, 14F

01/31 02:26, , 15F
只是想知道有沒有比較好的實作方式而已
01/31 02:26, 15F

02/15 14:08, , 16F
看到刪除自己做的時候我也是覺得很想罵髒話XD
02/15 14:08, 16F

02/23 10:57, , 17F
那本書是人家的博士論文啊... 刻論文的時候當然太麻煩的跳過
02/23 10:57, 17F

02/23 16:32, , 18F
印象裡博士論文跟後來出的書好像有點差? 有重新整理過
02/23 16:32, 18F
文章代碼(AID): #1Mh71UEo (PLT)
討論串 (同標題文章)
文章代碼(AID): #1Mh71UEo (PLT)