Применение seq для улучшения времени выполнения в 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, но я запутался.

Я знаю это:

  1. seq a b переводит a в слабую первую нормальную форму при оценке b
  2. Что выражение находится в слабой нормальной форме, если самое внешнее выражение является лямбдой или конструктором данных.

Любые указатели на то, какое понимание мне не хватает?


person rationalrevolt    schedule 03.11.2012    source источник
comment
Я думаю, что ваша главная проблема let n = nodes !! i. Индексация списка - O(i), поэтому, если Node имеет много соединений, moveZombie на нем квадратично по количеству Node. Если у вас много Node с множеством соединений, вы получите кубическую сложность для step. Попробуйте использовать Array вместо списка. (Если у вас есть больше, чем несколько Node, это не улучшит ситуацию, если у вас будет только два.)   -  person Daniel Fischer    schedule 03.11.2012
comment
Лично я предпочел бы Data.Sequence вместо Array.   -  person Ben Millwood    schedule 05.11.2012


Ответы (1)


Основная проблема скорости заключается в обработке «узлов» как списка — ваш алгоритм часто должен извлекать элементы в случайных позициях, а это O (n) для каждого поиска в структуре данных связанного списка.

Замена «узлов» с [Node] на любую более подходящую структуру данных (Data.Map или Array) значительно упростит задачу.

person Peteris    schedule 26.06.2013