應用以次提高執行時間在Haskell

我有以下幾點：應用以次提高執行時間在Haskell

data Node = Node { position::Int 
       , zombies::Float 
       , connections::[Int] 
       } 

moveZombie :: [Node] -> Node -> Node 
moveZombie nodes (Node i _ cx) = zc `seq` Node i zc cx 
    where zc = sum [zombies n/(fromIntegral $ length $ connections n) | i <- cx, let n = nodes !! i] 

step :: Int -> [Node] -> [Node] 
step 0 nodes = nodes 
step k nodes = step (k-1) $ map (moveZombie nodes) nodes

與GHC啓用分析編譯告訴我，成本中心：

       Individual 
COST CENTRE   MODULE %time %alloc 
moveZombie.zc   Main 60.3 90.4 
moveZombie.zc.n  Main 37.6 0.0

我試過如下：moveZombie nodes (Node i _ cx) = zc `seq` Node i zc cx強制嚴格的評估並讓程序運行得更快，但是完全沒有成功。我知道我對seq工作方式的理解有些問題，但我似乎無法弄清楚什麼。

我想，我需要迫使step k nodes = step (k-1) $ map (moveZombie nodes) nodes嚴格的評價，但我很困惑。

我知道：

seq a b力a到弱第一範式，評價b
時即表達是在弱正常形式，如果最外面的表達式是λ或數據構造

對我缺少什麼認識任何指針？

來源

2012-11-03 rationalrevolt

我認爲你的主要問題是'let n = nodes !! i'。列表索引是'O（i）'，所以如果'Node'有很多連接，那麼'moveZombie'是'Node'的數量的二次方。如果你有很多帶有許多連接的'Node'，你會得到一個'step'的立方體複雜度。嘗試使用'Array'而不是列表。（如果你有不止一個'節點'，如果你只有兩個節點，它不會改進。） –

我個人更喜歡'Data.Sequence'到'Array'。 –

主要的速度問題是處理「節點」作爲一個列表 - 你的算法往往需要在隨機位置獲取項目，這是一個鏈表數據結構每一個檢索爲O（n）。

更換從[節點]「節點」到任何更適合的數據結構（Data.Map，或陣列）將顯著提高了複雜性。

來源

2013-06-26 17:34:52 Peteris

應用以次提高執行時間在Haskell

回答

相關問題