13

显然Seq渐近地执行与所有可能的操作相同或更好[]的操作。但是由于它的结构比列表更复杂，对于小尺寸，它的恒定开销可能会使其变慢。我想知道多少钱，特别是：

  1. <|相比慢了:多少？
  2. Seq与折叠/遍历相比，折叠/遍历慢了多少[]（不包括折叠/遍历函数的成本）？
  3. \xs x -> xs ++ [x]变慢的大小（大约）是|>多少？
  4. ++变慢的大小（大约）是><多少？
  5. viewl与列表上的模式匹配相比，结果上的调用和模式匹配的成本是多少？
  6. 与-元素列表相比，-元素占用n多少内存？（不计算元素占用的内存，只计算结构。）Seqn

我知道这很难衡量，因为Seq我们谈论的是摊销复杂性，但我想至少知道一些粗略的数字。

4

2 回答 2

14

这应该是一个开始 - http://www.haskell.org/haskellwiki/Performance#Data.Sequence_vs._lists

一个序列使用的空间是等效列表的 5/6 到 4/3 倍（假设每个节点一个字的开销，如在 GHC 中）。如果只使用 deque 操作，空间使用量将接近范围的下限，因为所有内部节点都是三元的。大量使用 split 和 append 将导致序列使用与列表大致相同的空间。详细地：

  • 一个长度为 n 的列表由 n 个 cons 节点组成，每个节点占用 3 个单词。
  • 长度为 n 的序列具有大约 n/(k-1) 个节点，其中 k 是内部节点的平均数量（每个 2 或 3）。每个节点都有一个指针、一个大小和开销，以及每个元素的一个指针，即 n(3/(k-1) + 1) 个字。

对于头部（cons 和 head）的操作，List 是一个非常重要的常数因子，使其成为类堆栈和类流访问模式的更有效选择。Data.Sequence 对于其他所有访问模式（例如队列和随机访问）都更快。

于 2013-02-10T14:46:35.880 回答
1

我有一个更具体的结果要添加到上述答案中。我正在求解一个朗之万方程。我使用了 List 和 Data.Sequence。此解决方案中正在进行列表/序列后面的大量插入。

总而言之，我没有看到速度有任何提高，实际上使用序列时性能下降了。此外，使用 Data.Sequence，我需要增加 Haskell RTS 的可用内存。

因为我绝对不是优化的权威；我在下面发布了这两种情况。我很高兴知道这是否可以改进。-O2两个代码都是用标志编译的。

  1. 使用 List 的解决方案，大约需要 13.01 秒
  2. 使用 Data.Sequence 的解决方案，大约需要 15.13 秒
于 2014-10-31T16:44:09.940 回答