Data.Sequence.Seq与[]相比有多快？

对于所有可能的操作，显然Seq渐近地执行与[]相同或更好。但是由于其结构比列表更复杂，对于小尺寸的系统而言，其不断的开销可能会使其变慢。我想知道有多少，特别是：Data.Sequence.Seq与[]相比有多快？

被<|相比:慢多少？
折叠/穿越Seq与折叠/穿越[]（不包括折叠/穿越功能的成本）相比，要慢多少？
\xs x -> xs ++ [x]变得比|>慢什么尺寸（大约）？
++变得慢于><的尺寸（大约）是多少？
与列表中的模式匹配相比，调用viewl和结果上的模式匹配的成本是多少？
n -element Seq占用多少内存相比n -lelement list？（不计算由元素，只有结构所占用的内存。）

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

来源

2013-02-10 Petr Pudlák

没有这样的比较存在。我建议使用标准基准库自己生成它。 – 2013-02-10 14:35:20

如果有人最终决定在这个基准上进行基准测试，那么为了比较而放入一个“Vector”也是很有意义的。会很高兴看到结果。收藏这个。 – 2013-02-10 14:38:04

由于在真实代码中使用GHC，中间列表往往会融合并重写并消失，这使得它们更像控制结构而不是数据结构本身，这也很困难（或不是特别有用）。 – jberryman 2013-02-10 21:51:27

这应该是一个开始 - 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）的平均arity。每个节点都有一个指针，一个大小和开销，加上每个元素的指针，即n（3 /（k-1）+ 1）个字。

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

来源

2013-02-10 14:46:35 manojlds

我还有一个具体的结果添加到上面的答案。我正在解决一个朗之万方程。我使用List和Data.Sequence。在此解决方案中，列表/序列后面的很多插入操作正在进行。总之，我没有看到速度有任何提高，实际上性能随着序列而恶化。此外，与Data.Sequence，我需要增加可用于Haskell RTS的内存。

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

Solution with List，需要约13.01秒
Solution with Data.Sequence，需要约15.13秒

来源

2014-10-31 16:44:09 Dilawar

你的序列/列表有多长？ – 2014-11-02 15:20:21

他们俩都有10^6个元素。 – Dilawar 2014-11-04 08:05:42

如果有人在这里，我测试链接的代码出于好奇，并在我的机器seq稍快。（〜5％）这也是一个不好的例子，因为在这两个案例中，比较归结为通过在前面添加并倒转来建立清单。或者通过在最后添加Seq然后将其转换为列表而不是直接使用它来构建Seq。但即使在我的机器列表中速度较慢，所以我想象不是由数据结构的选择造成的速度差异，而是代码中的其他变化。 – 2016-07-27 23:24:14

Data.Sequence.Seq与[]相比有多快？

回答

相关问题