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

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

与<|相比，:慢多少？

折叠/遍历Seq与折叠/遍历[]相比要慢多少(不包括折叠/遍历功能的成本)？

\xs x -> xs ++ [x]比|>变慢的大小(大约)？

++比><变慢的大小(大约)？

与列表上的模式匹配相比，在结果上调用viewl和模式匹配的成本是多少？

与n -element列表相比，Seq -element n占用多少内存？ (不计算元素占用的内存，仅计算结构。)

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

最佳答案

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

序列使用的空间是等效列表的5/6到4/3倍(假设每个节点的开销如GHC中那样)。如果仅使用双端队列操作，则空间使用量将接近范围的下限，因为所有内部节点都是三元的。大量使用split和append将导致序列使用与列表大致相同的空间。详细:

长度为n的列表由n个cons节点组成，每个节点占用3个单词。

长度为n的序列具有大约n /(k-1)个节点，其中k是内部节点的平均Arity(每个2或3)。有一个指针，每个节点的大小和开销以及每个元素的指针，即n(3 /(k-1)+1)个字。

对于在头(缺点和头)上的操作，List是一个非平凡的常数因子，因此对于类似堆栈和类似流的访问模式而言，它是更有效的选择。对于其他所有访问模式(例如队列和随机访问)，Data.Sequence都更快。

关于performance - Data.Sequence.Seq与[]相比有多快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14798613/