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 b在评估时强制a进入弱第一范式b
  2. 如果最外面的表达式是 lambda 或 Data 构造函数，则表达式为弱范式

任何指向我缺少什么理解的指针？

4

1 回答 1

1

主要的速度问题是将“节点”视为一个列表 - 您的算法通常需要在随机位置获取项目，这对于链表数据结构中的每次检索都是 O(n)。

将 [Node] 中的“节点”替换为任何更适合的数据结构（Data.Map 或 Array）将显着提高复杂性。

于 2013-06-26T17:34:52.407 回答