haskell - 在haskell中搜索序列是否比向量快？

Question

除了列表之外，我在 Haskell 中使用数据结构是一种新人。我的目标是在 Data.Vector、Data.Sequence、Data.List 等中选择一个容器……我的问题如下:

我必须创建一个序列(从数学上讲)。序列从 0 开始。在每次迭代中，都会生成两个新元素，但根据第一个元素是否已经在序列中，只应附加一个元素。所以在每次迭代中都会调用 elem 函数(参见下面的伪代码)。

appendNewItem :: [Integer] -> [Integer]
appendNewItem acc = let firstElem  = someFunc
                        secondElem = someOtherFunc
                        newElem    = if firstElem `elem` acc 
                                        then secondElem
                                        else firstElem
                    in  acc `append` newElem

sequenceUptoN :: Int -> [Integer]
sequenceUptoN n = (iterate appendNewItem [0]) !! n

append 和 iterate 函数的位置取决于您使用的集合(为简单起见，我在类型签名中使用列表)。

问题是:我应该使用哪种数据结构？由于手指树的内部结构，Data.Sequence 是否更快地完成此任务？

非常感谢!!

Answer 1

不，序列的搜索速度并不快。 Vector 只是一 block 平坦的内存，通常可以提供最佳的查找性能。如果要优化搜索，请使用 Data.Vector.Unboxed。 (普通的“盒装”变体也很不错，但它实际上只包含对平面内存块中元素的引用，因此查找速度没有那么快。)

然而，由于平坦的内存布局，Vectors 不适合(纯功能)追加:基本上，每当您添加一个新元素时，整个必须复制数组，以免使旧数组无效(其他人可能仍在使用)。如果您需要追加，Seq 是一个不错的选择，尽管它不如 破坏性 追加快:为了获得最佳性能，您需要预先分配一个未初始化的Data.Vector.Unboxed.Mutable.MVector所需大小，使用 ST monad 填充它，然后卡住结果。但这比纯粹的功能替代品要复杂得多，所以除非你需要挤出每一点性能，Data.Sequence 是要走的路。如果您只是想追加元素，而不是查找元素，那么反向顺序的普通旧列表也可以解决问题。