2008/07/23

分開

承接上次的 Haskell 效能測試,我突然想到應該把 IO code 和 pure code 再分清楚一點,讓 State monad 單純傳回 list of results,最後用個 foldr 把這個 list 轉成一串 IO () 再全部接起來執行。因為 Haskell 的 laziness,這樣寫的執行期表現和上次沒什麼差別。

 1: import Control.Monad.State
 2: 
 3: cycleLength 1 k = k
 4: cycleLength n k | even n    = cycleLength (n `div` 2) $! (k + 1)
 5:                 | otherwise = cycleLength (3 * n + 1) $! (k + 1)
 6: 
 7: driver :: State [Int] [Int]
 8: driver = do eof <- gets null
 9:             if eof then return []
10:                    else do this <- commit
11:                            remains <- driver
12:                            return (this : remains)
13: 
14: commit :: State [Int] Int
15: commit = do i <- nextInt
16:             j <- nextInt
17:             return
18:               (maximum . map (flip cycleLength 1) $ [min i j .. max i j])
19:          where nextInt = State $ \(x : xs) -> (x, xs)
20: 
21: main = getContents >>= foldr ((>>) . print) (return ()) .
22:                        evalState driver . map read . words
驚人的是單單這樣改一下就讓執行時間下降到 0.6--0.7 秒,和 Java 不相上下!現在我的偏心得到 justification 了 XD。

--
而且現在我也覺得 IO monad 和 State monad 相處得比較融洽了 XD。

Labels:

Blogger yen37/23/2008 9:07 am 說:

看來你很在意偏心那句話...XD

不過同時,我也為Haskall的效率感到驚訝。比較好奇的是,初學者要花多久才能寫出這樣子的程式碼呢?

 

<< 回到主頁