在包含双打的集合(为简单起见,称之为列表)的数据结构上考虑这个顺序过程.只要我愿意,做： 随机从结构中选择两个不同的列表 根据这些列表计算统计量 根据该统计信息翻转硬币 根据
>随机从结构中选择两个不同的列表
>根据这些列表计算统计量
>根据该统计信息翻转硬币
>根据掷硬币的结果,可能修改其中一个列表
目标是最终实现收敛,因此“解决方案”在迭代次数上是线性的.可以在SO问题here中看到此过程的实现,这是一个直观的可视化：
似乎可以更好地执行此过程 – 也就是说,通过使用多个工作程序在不同的OS线程上并发执行,可以更快地实现收敛,例如：
我想一个完美实现的应该能够在O(n / P)时间内实现解决方案,P是可用计算资源的数量.
阅读Haskell并发性已经让我的头脑旋转了MVar,TVar,TChan,酸状态等等.似乎很明显,这个程序的并发实现与the one I linked above看起来非常不同.但是,程序本身似乎基本上是一个非常温和的算法,基本上是一个内存数据库,这是一个我以前确定有人遇到过的问题.
我猜我将不得不使用某种可变的并发数据结构来支持体面的随机访问(即随机空闲元素)&修改.当我试图将所有可能需要的东西拼凑在一起以提高性能时(例如,STM看起来很可疑),我有点迷失了.
如果目标是对顺序实现的性能提升,那么哪种数据结构,并发概念等适用于此类任务？
把事情简单化：> forkIO用于轻量级,超便宜的螺纹.
> MVar,用于快速,线程安全的共享内存.
>和适当的序列类型(可能是vector,如果你只是前置,可能是列表)
>一个很好的stats包
>和一个快速随机数源(例如mersenne-random-pure64)
你可以稍后尝试更高级的东西.对于原始性能,首先要保持简单：保持锁定数量(例如每个缓冲区一个);确保编译代码并使用线程运行时(ghc -O2),你应该有一个良好的开端.
RWH有一个cover the basics并发Haskell的介绍章节.