1

私は次のものを持っています：

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が、混乱しています。

そんなこと知ってる：

  1. seq a ba評価時に弱い第 1 正規形を強制するb
  2. 最も外側の式がラムダまたはデータ コンストラクターである場合、式は弱正規形であること

私が見逃している理解への指針はありますか？

4

1 に答える 1

1

主な速度の問題は、「ノード」をリストとして扱うことです。アルゴリズムは、多くの場合、ランダムな位置でアイテムをフェッチする必要があり、リンクされたリスト データ構造での検索ごとに O(n) になります。

「ノード」を [Node] からより適切なデータ構造 (Data.Map または Array) に置き換えると、複雑さが大幅に改善されます。

于 2013-06-26T17:34:52.407 に答える