arrays - Haskell 实时更新和查找性能

Question

我正在编写一个玩游戏的 ai (aichallenge.org - Ants)，它需要大量更新和引用数据结构。我已经尝试过数组和 map ，但基本问题似乎是每次更新都会创建一个新值，这使得它变慢了。如果您采取行动的时间超过一秒钟，游戏就会将您引导出去，因此该应用程序被视为“硬实时”。是否有可能在 Haskell 中获得可变数据结构的性能，或者我应该学习 Python，还是在 OCaml 中重写我的代码？

我已经完全重写了 Ants “starter-pack”。从数组更改为 map ，因为我的测试表明 map 更新得更快。

我在配置文件的情况下运行 map 版本，这表明仅 map 更新就占用了大约 20% 的时间。

这是一个简单的演示 Array 更新有多慢。

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不是最佳的，你需要自己动手。

其次，您应该使用 profiler找到性能问题所在，而不是依靠挥手。 Haskell 代码通常比 Python 快得多(快 10-30 倍，您可以查看 Language Shootout 例如比较)，即使使用函数式数据结构也是如此，因此您可能做错了什么。

haskell supports mutable data很不错。见 ST (状态线程)和 ST 的可变数组库.也看看vectors包裹。最后，您可以使用数据并行的haskell、haskell-mpi 或other ways of parallelization加载所有可用的 CPU 内核，甚至将工作分配到多台计算机上。

您是使用编译后的代码(例如 cabal build 或 ghc --make )还是使用 runhaskell或 ghci ?后者是字节码解释器，创建的代码比 native 代码编译器慢得多。见 Cabal reference - 它是构建应用程序的首选方式。

还要确保您已启用优化( -O2 和 other flags )。请注意 -O对比 -O2可以有所作为，并尝试不同的后端，包括新的 LLVM 后端 (-fllvm)。