У меня есть следующее:
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
- Что выражение находится в слабой нормальной форме, если самое внешнее выражение является лямбдой или конструктором данных.
Любые указатели на то, какое понимание мне не хватает?
let n = nodes !! i
. Индексация списка -O(i)
, поэтому, еслиNode
имеет много соединений,moveZombie
на нем квадратично по количествуNode
. Если у вас многоNode
с множеством соединений, вы получите кубическую сложность дляstep
. Попробуйте использоватьArray
вместо списка. (Если у вас есть больше, чем несколькоNode
, это не улучшит ситуацию, если у вас будет только два.) - person Daniel Fischer   schedule 03.11.2012Data.Sequence
вместоArray
. - person Ben Millwood   schedule 05.11.2012