Vin*_*ara 7 optimization haskell vector data-structures
我正在尝试使用Haskell来计算统计物理中模型的分区函数.这涉及遍历相当大的配置列表并总结各种可观察量 - 我希望尽可能高效地完成.
我的代码的当前版本在这里:https://gist.github.com/2420539
尝试在列表和向量之间进行选择以枚举配置时会发生一些奇怪的事情; 特别是,截断列表,使用V.toList . V.take (3^n) . V.fromList(where Vis Data.Vector)比使用更快take,这感觉有点违反直觉.在这两种情况下,列表都会被懒惰地评估.
列表本身是使用iterate; 如果相反,我Vector尽可能多地使用s并使用构建列表V.iterateN,再次变得更慢......
我的问题是,有没有办法(除了拼接V.toList和V.fromList代码中的随机位置)预测哪一个最快？(顺便说一句,我使用ghc -O2当前的稳定版本编译所有内容.)
Don*_*art 12
向量是严格的,并且具有O(1)子集(例如,取).它们还具有优化的插入和删除功能.因此,您有时会通过动态切换数据结构来看到性能改进.但是,这通常是错误的方法 - 将所有数据保持为一种形式或另一种形式更好.(而且你也在使用UArrays - 进一步混淆了这个问题).
通用规则:
如果数据很大并且只是以大量方式进行转换,那么使用像矢量这样的密集,高效的结构是有意义的.
如果数据很小,并且线性地遍历,很少,那么列表是有意义的.
请记住,列表和向量上的操作具有不同的复杂性,因此虽然iterate . replicate在列表上是O(n),但是懒惰,向量上的相同不一定有效(您应该更喜欢向量中的内置方法来生成数组).
通常,矢量应始终更好地用于数值运算.可能是您必须使用在列表中执行的不同功能.
我会坚持只有矢量.避免使用UArrays,并避免使用除生成器之外的列表.