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

Question

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

1. 如何慢得多的<|比较:？
2. Seq与折叠/遍历相比,折叠/遍历的速度要慢多少[](不包括折叠/遍历功能的成本)？
3. 大小(大约)\xs x -> xs ++ [x]变得比|>什么慢？
4. 大小(大约)++变得比><什么慢？
5. viewl与列表上的模式匹配相比,结果上的调用和模式匹配的成本是多少？
6. 与元素列表相比,n元素Seq占用了多少内存n？(不计算元素占用的内存,只计算结构.)

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

Answer 1

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

序列使用的空间是等效列表的5/6和4/3倍(假设每个节点有一个字的开销,如GHC).如果仅使用deque操作,则空间使用将接近范围的下端,因为所有内部节点都将是三元组.大量使用拆分和追加将导致序列使用与列表大致相同的空间.详细地:

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

对于头部(cons和head)的操作,List是一个非常重要的常量因子,使其成为类似堆栈和类似流的访问模式的更有效选择.对于每个其他访问模式,Data.Sequence更快,例如队列和随机访问.