Обновление и поиск в реальном времени на Haskell

Question

Я пишу игровой ai (aichallenge.org - Ants), который требует много обновлений и ссылаюсь на структуры данных.Я пробовал и массивы, и карты, но основная проблема заключается в том, что каждое обновление создает новое значение, что замедляет его.Игра загружает вас, если на ваш ход уходит более одной секунды, поэтому приложение считается «жестким в реальном времени».Возможно ли иметь производительность изменчивых структур данных в Haskell, или я должен изучать Python, или переписать свой код в OCaml?

Я полностью переписал «стартовый пакет» муравьев.Изменено с Массивов на Карты, потому что мои тесты показали, что Карты обновляются намного быстрее.

Я запустил версию Карты с включенным профилированием, которая показала, что около 20% времени уходит только на обновления карты.

Вот простая демонстрация медленных обновлений массива.

slow_array =
    let arr = listArray (0,9999) (repeat 0)
        upd i ar = ar // [(i,i)]
    in  foldr upd arr [0..9999]

Теперь оцениваем slow_array! 9999 занимает почти 10 секунд!Несмотря на то, что было бы быстрее применить все обновления сразу, пример моделирует реальную проблему, когда массив должен обновляться каждый ход, и предпочтительно каждый раз, когда вы выбираете ход при планировании следующего хода.

---

Спасибо nponeccop и Tener за ссылку на векторные модули.Следующий код эквивалентен моему первоначальному примеру, но выполняется за 0,06 секунды вместо 10.

import qualified Data.Vector.Unboxed.Mutable as V

fast_vector :: IO (V.IOVector Int)
fast_vector = do
  vec <- V.new 10000
  V.set vec 0
  mapM_ (\i -> V.write vec i i) [0..9999]
  return vec

fv_read :: IO Int
fv_read  = do
  v <- fast_vector
  V.read v 9999

Теперь, чтобы включить это в мой код Ants ...

Answer 1

Прежде всего, подумайте, сможете ли вы улучшить свой алгоритм. Также обратите внимание, что значение по умолчанию Ants.hs не оптимально, и вам нужно бросить свой собственный.

Во-вторых, вы должны использовать профилировщик , чтобы определить, где проблема с производительностью, вместо того, чтобы полагаться на размахивание руками. Код на Haskell обычно намного быстрее, чем Python (в 10-30 раз быстрее, вы можете посмотреть Language Shootout для сравнения) даже с функциональными структурами данных, поэтому, вероятно, вы делаете что-то не так.

Haskell очень хорошо поддерживает изменяемые данные . См. ST (поток состояний) и библиотеки для изменяемых массивов для ST. Также взгляните на векторов пакет. Наконец, вы можете использовать параллельный к данным haskell, haskell-mpi или другие способы распараллеливания для загрузки всех доступных ядер ЦП или даже распределить работу по нескольким компьютерам.

Вы используете скомпилированный код (например, cabal build или ghc --make) или используете runhaskell или ghci? Последние являются интерпретаторами байт-кода и создают гораздо более медленный код, чем компилятор нативного кода. См. Ссылка Cabal - это предпочтительный способ создания приложений.

Также убедитесь, что у вас включена оптимизация (-O2 и другие флаги ). Обратите внимание, что -O против -O2 может изменить ситуацию, и попробуйте разные бэкэнды, включая новый бэкэнд LLVM (-fllvm).

Answer 2

Обновление массивов по одному элементу за раз невероятно неэффективно, потому что каждое обновление включает в себя создание копии всего массива.Другие структуры данных, такие как Map, реализованы в виде деревьев и, таким образом, позволяют обновлять логарифмическое время.Тем не менее, при общем обновлении функциональных структур данных один элемент за один раз часто оказывается неоптимальным, поэтому вам следует попытаться сделать шаг назад и подумать о том, как можно реализовать что-то как преобразование всей структуры сразу, а не одного элемента.за один раз.

Например, ваш пример slow_array может быть записан гораздо эффективнее, если все обновления выполняются за один шаг, для которого требуется только один раз скопировать массив.

faster_array =
    let arr = listArray (0,9999) (repeat 0)
    in  arr // [(i,i) | i <- [0..9999]]

Если вы не можете придумать альтернативу императивному алгоритму «один элемент за раз», изменяемые структуры данных были упомянуты в качестве другого варианта.

Answer 3

Вы в основном запрашиваете изменяемую структуру данных. Помимо стандартных библиотек, я бы порекомендовал вам поискать это:

• вектор: http://hackage.haskell.org/package/vector

Тем не менее, я не уверен, что они вам нужны. Есть четкие алгоритмы для персистентных структур данных. Быстрая замена Data.Map - хеш-таблица из этого пакета:

• неупорядоченные контейнеры: http://hackage.haskell.org/package/unordered-containers