爲什麼函數的結果沒有被重用？

當我嘗試編碼最短路徑算法時，我遇到了一個奇怪的事情。函數floydWarshall函數以數組形式生成adjecency矩陣後，main函數嘗試多次查詢數組（在replicateM_循環中）。爲什麼函數的結果沒有被重用？

我發現我的代碼非常慢。所以我把traceShow "doing"放在floydWarshall的頂部，然後重新找到每個res ! (start,end)重複調用floydWarshall。

爲什麼數組每次都會重新生成？

完整的源與樣本輸入：https://gist.github.com/cwyang/27ab81bee731e6d01bb3a7483fdb748e

floydWarshall :: AdjMatrix (Maybe Int) -> AdjMatrix (Maybe Int) 
floydWarshall am = traceShow "doing" $ runST $ do 
    arr <- thaw am :: ST s (STArray s (Vertex,Vertex) (Maybe Int)) 
    sequence_ [ go arr k i j | k <- r, i <- r, j <- r] 
    freeze arr 
    where ((minb,_), (maxb,_)) = bounds am 
     r = [minb..maxb] 
     go :: STArray s (Vertex,Vertex) (Maybe Int) 
      -> Vertex -> Vertex -> Vertex -> ST s() 
     go arr k i j = do 
      ij <- readArray arr (i,j) 
      ik <- readArray arr (i,k) 
      kj <- readArray arr (k,j) 
      case (ik, kj) of 
      (Nothing, _) -> return() 
      (_, Nothing) -> return() 
      (Just a, Just b) -> case ij of 
       Nothing -> do 
       writeArray arr (i,j) $ Just (a+b) 
       (Just c) -> when (c > a+b) $ do 
       writeArray arr (i,j) $ Just (a+b) 
readInt :: B.ByteString -> Int 
readInt = fst . fromJust . B.readInt 

main :: IO() 
main = do 
    [n,m] <- rl 
    edges <- replicateM m $ do 
    [from,to,weight] <- rl 
    return (from,to,weight) 
    [q] <- rl 
    let am = buildAdjMatrix (1,n) edges 
     res= floydWarshall am 
    replicateM_ q $ do 
    [start,end] <- rl 
    putStrLn . show $ maybe (-1) id (res ! (start,end)) 
    where rl = map readInt . B.words <$> B.getLine

採樣運行：

$ graph < floyd3.txt hs 
"doing"  <-- floydWarshall keeps calling 
1395 
"doing" 
975 
"doing" 
1593 
"doing" 
1023 
"doing" 
1521 
...

來源

2016-11-01 Chul-Woong Yang

任何機會你有完整的代碼在線？理想情況下，您需要查看核心輸出以查看正在發生的情況，但這僅適用於編譯的內容。另外，你在編譯時使用了哪些標誌？ – Alec

Floyd-Warshall是經典的動態規劃算法。你可以找到更好的方法來解決這個問題，使用_Haskell_在這篇文章中：http://jelv.is/blog/Lazy-Dynamic-Programming/ – Shersh

我已經上傳完整的代碼和示例輸入：https：//gist.github。 com/cwyang/27ab81bee731e6d01bb3a7483fdb748e –

無奈的是，這似乎是由GHC問題"Costly let binding gets duplicated in IO action value"引起的。

使用forM_而不是replicateM_或使用BangPatterns可解決此問題。

來源

2016-11-01 11:22:37

@上面的Shersh的評論看起來相當不錯：「在這篇文章中你可以找到更好的方法來解決這些使用Haskell的問題：jelv.is/blog /懶惰動態編程「一般來說，在IO monad中，你應該儘可能少做...編程Haskell時你需要改變一下你的想法，但隨着時間的推移，你會越來越喜歡它：） – mb21

哦，哇，這是一個討厭的陷阱。這是我至少不知道的一個問題，我已經將Haskell用作我近十年來新項目的首選語言，其中包括幾年來專攻Haskell項目的項目。也許這是一些小的證據，表明這個問題並不常見。 –

@ mb21雖然我同意你評論的精神，但是OP不是在'IO' monad內部工作，而是在'ST' monad內部工作（這個bug實際上並不在算法中，而是在調用的代碼中它）。另外，由於這種特殊算法需要大量更新，因此'ST'似乎是一個不錯的選擇。 – Alec

爲什麼函數的結果沒有被重用？

回答

相關問題