optimization - Haskell:列表/向量/数组性能调优

Question

我正在尝试使用 Haskell 来计算统计物理学中模型的配分函数。这涉及遍历相当大的配置列表并对各种可观察值求和——我希望尽可能高效地做到这一点。

我的代码的当前版本在这里:https://gist.github.com/2420539

尝试在列表和向量之间进行选择以枚举配置时会发生一些奇怪的事情；特别是要截断列表，使用 V.toList . V.take (3^n) . V.fromList (其中 V 是 Data.Vector )比仅使用 take 更快，感觉有点反直觉。在这两种情况下，列表都是惰性评估的。

列表本身是使用 iterate 构建的。 ;如果我改为使用 Vector s 并使用 V.iterateN 构建列表，又变慢了……

我的问题是，有没有办法(除了拼接 V.toList 和 V.fromList 在代码中的随机位置)来预测哪个最快？ (顺便说一句，我使用 ghc -O2 用当前稳定版本编译所有内容。)

Answer 1

向量是严格的，并且有 O(1) 个子集(例如 take)。它们还具有优化的插入和删除。因此，您有时会看到通过动态切换数据结构来提高性能。然而，这通常是错误的方法——将所有数据保持在一种形式或另一种形式更好。 (而且您也在使用 UArrays - 进一步混淆了这个问题)。

通用规则:

如果数据很大并且仅以批量方式进行转换，则使用密集、高效的结构(如向量)是有意义的。

如果数据很小，并且很少线性遍历，那么列表是有意义的。

请记住，列表和向量上的操作具有不同的复杂性，因此 iterate . replicate在列表上是 O(n)，但是很懒惰，同样的向量上的效率不一定一样高(你应该更喜欢向量中的内置方法来生成数组)。

一般来说，向量应该总是更适合数值运算。可能您必须使用在列表中执行的不同功能。

我只会坚持使用向量。避免使用 UArray，并避免使用列表作为生成器。