Data.Vector会替换Data.Sequence吗？

Question

我一直很喜欢Data.Sequence.但是,由于我一直在学习Data.Vector,它似乎可以做Data.Sequence可以做的一切,但更好,再加上它可以做更多的东西.我们应该弃用Data.Sequence并讲道Data.Vector吗？在Data.Vector上使用Data.Sequence有什么好的理由吗？

Answer 1

这些数据结构都不能取代另一个; Data.Sequence并且Data.Vector实际上是可用于表示序列的数据结构的完全相反的两端.

• Data.Vector是一个连续的元素数组.这意味着小内存占用和O(1)查找,但可怕的突变,连接和复制(每个O(n)).(如果你删除持久性,变异可以是O(1).)
• Data.Sequence另一方面,它是一个纯粹的功能树.这意味着更高的内存使用率和更少的局部性,但它支持快速访问和突变O(log n)和令人敬畏的串联O(log(min(n1,n2)))和复制.

数据结构的选择实际上取决于此处的任务.

• 以线性方式或随机查找处理大量元素流最好用Data.Vector.
• 如果您需要拆分,连接和更改元素,请使用Data.Sequence.