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 回答