7

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

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

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

列表本身是使用iterate;构建的 相反，如果我Vector尽可能多地使用 s 并通过 using 构建列表V.iterateN，那么它再次变得更慢......

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

4

1 回答 1

12

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

一般规则：

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

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

请记住，列表和向量上的操作具有不同的复杂性，因此虽然iterate . replicate在列表上是O(n)，但是是惰性的，但对向量的相同操作不一定会那么有效（您应该更喜欢向量中的内置方法来生成数组）。

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

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

于 2012-04-19T12:24:45.610 回答