haskell - 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 .