Haskell 实时更新和查找性能
我正在编写一个游戏人工智能（aichallenge.org - Ants），它需要大量更新和引用数据结构。我已经尝试过数组和映射，但基本问题似乎是每次更新都会创建一个新值，这使得速度变慢。如果您移动的时间超过一秒，游戏就会将您退出，因此该应用程序被视为“硬实时”。 Haskell 中是否有可能具有可变数据结构的性能，或者我应该学习 Python，或者用 OCaml 重写我的代码？
我已经完全重写了 Ant 的“starter-pack”。从数组更改为地图，因为我的测试表明地图更新速度更快。
我运行了启用了分析的地图版本，结果显示大约 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 代码中...
I am writing a game-playing ai (aichallenge.org - Ants), which requires a lot of updating of, and referring to data-structures. I have tried both Arrays and Maps, but the basic problem seems to be that every update creates a new value, which makes it slow. The game boots you out if you take more than one second to make your move, so the application counts as "hard-real-time". Is it possible to have the performance of mutable data-structures in Haskell, or should I learn Python, or rewrite my code in OCaml?
I have completely rewritten the Ants "starter-pack". Changed from Arrays to Maps because my tests showed that Maps update much faster.
I ran the Maps version with profiling on, which showed that about 20% of the time is being taken by Map updates alone.
Here is a simple demonstration of how slow Array updates are.
slow_array =
let arr = listArray (0,9999) (repeat 0)
upd i ar = ar // [(i,i)]
in foldr upd arr [0..9999]
Now evaluating slow_array!9999 takes almost 10 seconds! Although it would be faster to apply all the updates at once, the example models the real problem where the array must be updated each turn, and preferably each time you choose a move when planning your next turn.
Thanks to nponeccop and Tener for the reference to the vector modules. The following code is equivalent to my original example, but runs in 0.06 seconds instead of 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
Now, to incorporate this into my Ants code...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，想想是否可以改进你的算法。另请注意，默认的
Ants.hs并不是最佳选择，您需要自行设计。其次，您应该使用 分析器 来查找性能问题出在哪里，而不是依赖挥手。 Haskell 代码通常比 Python 快得多（快 10-30 倍，你可以查看 语言大战（例如比较），即使是函数式数据结构，所以你可能做错了什么。
Haskell 很好地支持可变数据。请参阅
ST（状态线程）和ST的可变数组库。另请查看 vectors 包。最后，您可以使用数据并行 haskell、haskell-mpi 或其他并行化方式加载所有可用的 CPU 核心，甚至将工作分配到多台计算机上。您使用的是编译代码（例如
cabal build或ghc --make）还是使用runhaskell或ghci？后者是字节码解释器，创建的代码比本机代码编译器慢得多。请参阅 Cabal 参考 - 这是构建应用程序的首选方式。另请确保您已启用优化（
-O2和 其他标志）。请注意，-O与-O2可能会有所不同，并尝试不同的后端，包括新的 LLVM 后端 (-fllvm)。First of all, think if you can improve your algorithm. Also note that the default
Ants.hsis not optimal and you need to roll your own.Second, you should use a profiler to find where the performance problem is instead of relying on hand-waving. Haskell code is usually much faster than Python (10-30 times faster, you can look at Language Shootout for example comparison) even with functional data structures, so probably you do something wrong.
Haskell supports mutable data pretty well. See
ST(state thread) and libraries for mutable arrays for theST. Also take a look at vectors package. Finally, you can use data-parallel haskell, haskell-mpi or other ways of parallelization to load all available CPU cores, or even distribute work over several computers.Are you using compiled code (e.g.
cabal buildorghc --make) or userunhaskellorghci? The latter ones are bytecode interpreters and create much slower code than the native code compiler. See Cabal reference - it is the preferred way to build applications.Also make sure you have optimization turned on (
-O2and other flags). Note that-Ovs-O2can make a difference, and try different backends including the new LLVM backend (-fllvm).一次更新数组一个元素的效率极其低下，因为每次更新都涉及复制整个数组。其他数据结构（例如 Map）被实现为树，因此允许对数时间更新。然而，一般来说，一次更新一个元素的功能数据结构通常不是最佳的，因此您应该尝试退后一步，思考如何一次性实现整个结构而不是单个元素的转换一次。
例如，您的
slow_array示例可以通过一步完成所有更新来更高效地编写，这只需要复制一次数组。如果您无法想到命令式一次一个元素算法的替代方案，可变数据结构被认为是另一种选择。
Updating arrays one element at a time is incredibily inefficient because each update involves making a copy of the whole array. Other data structures such as
Mapare implemented as trees and thus allow logarithmic time updates. However, in general updating functional data structures one element at a time is often sub-optimal, so you should try to take a step back and think about how you can implement something as a transformation of the whole structure at once instead of a single element at a time.For example, your
slow_arrayexample can be written much more efficiently by doing all the updates in one step, which only requires the array to be copied once.If you cannot think of an alternative to the imperative one-element-at-a-time algorithm, mutable data structures have been mentioned as another option.
您基本上是在要求可变的数据结构。除了标准库之外，我建议您查找以下内容：
，我不太确定你是否需要它们。对于持久数据结构也有简洁的算法。 Data.Map 的快速替代品是来自此包的哈希表：
You are basically asking for mutable data structure. Apart from standard libraries I would recommend you lookup this:
That said, I'm not so sure that you need them. There are neat algorithms for persitent data structures as well. A fast replacement for Data.Map is hash table from this package: