什么容器真的模仿Haskell中的std :: vector？

Question

问题

我正在寻找一个容器,用于保存n - 1问题的部分结果,以便计算n第一个问题.这意味着容器的大小始终是n.

i容器的每个元素取决于至少2个和最多4个先前的结果.

容器必须提供:

• 开始或结束时的恒定时间插入(两者之一,不一定都是)
• 中间的恒定时间索引

或者(给定O(n)初始化):

• 恒定时间单元素编辑
• 中间的恒定时间索引

std::vector它是什么以及为什么相关

对于那些不了解C++的人来说,std::vector是一个动态大小的数组.它非常适合这个问题,因为它能够:

• 建设中的储备空间
• 在中间提供恒定时间索引
• 最后提供恒定时间插入(带有预留空间)

因此O(n),在C++中,这个问题在复杂性方面是可以解决的.

为什么Data.Vector不呢std::vector

Data.Vector与...一起Data.Array提供类似的功能std::vector,但不完全相同.当然,两者都在中间提供恒定的时间索引,但它们既不提供恒定的时间修改((//)例如至少O(n)),也不提供在任何一个开始时的恒定时间插入.

结论

什么容器真的模仿std::vectorHaskell？或者,什么是我最好的镜头？

Answer 1

从reddit提出使用的建议Data.Vector.constructN:

O(n)通过将生成器函数重复应用于向量的已构造部分来构造具有n个元素的向量.

 constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>

例如:

? import qualified Data.Vector as V
? V.constructN 10 V.length
fromList [0,1,2,3,4,5,6,7,8,9]
? V.constructN 10 $ (1+) . V.sum
fromList [1,2,4,8,16,32,64,128,256,512]
? V.constructN 10 $ \v -> let n = V.length v in if n <= 1 then 1 else (v V.! (n - 1)) + (v V.! (n - 2))
fromList [1,1,2,3,5,8,13,21,34,55]

正如您在上面所描述的那样,这似乎有资格解决问题.

Answer 2

我想到的第一个数据结构是Maps from Data.Map或Sequences from Data.Sequence.

更新

Data.Sequence

序列是持久数据结构,允许大多数操作有效,同时仅允许有限序列.如果您感兴趣,它们的实现基于指树.但它有哪些特质？

• O(1)计算长度
• O(1) /插入在正面背面与运营商<|和|>分别.
• 从列表中创建O(n)fromlist
• 对于长度为n1和n2的序列,O(log(min(n1,n2)))级联.
• O(log(min(i,ni)))索引i长度为n的序列中位置的元素.

此外,这种结构支持很多的你会从列表状结构期望已知的和方便的功能:replicate,zip,null,scanS, ,sort,,take 等等.由于这些相似之处,您必须执行限定导入或隐藏具有相同名称的函数.dropsplitAtPrelude

Data.Map

Maps是实现"事物"之间对应关系的标准主力,你可以称之为Hashmap或其他编程语言中的关联数组在Haskell中被称为Maps; 除了说Python Maps是纯粹的 - 所以更新会给你一个新的Map并且不会修改原始实例.

地图有两种风格 - 严格和懒惰.

引用文档

严格

该模块的API在键和值中都是严格的.

懒

该模块的API在键中是严格的,但在值中是懒惰的.

因此,您需要选择最适合您应用的选项.您可以尝试使用两种版本和基准测试criterion.

而不是列出Data.Map我想传递给的功能

Data.IntMap.Strict

哪个可以利用键是整数的事实来挤出更好的性能从我们首先注意到的文档中引用:

许多操作的最坏情况复杂度为O(min(n,W)).这意味着操作可以在元素数量上变为线性,最大值为W - Int(32或64)中的位数.

那么有什么特点呢？ IntMaps

• 对于(不安全)索引的O(min(n,W)),(!)如果密钥/索引不存在则会出现错误,这是不安全的.这与行为相同Data.Sequence.
• O(n)计算size
• O(min(n,W))用于安全索引lookup,Nothing如果找不到密钥,则返回a ,Just a否则返回.
• O(分钟(N,W))为insert,delete,adjust和update

因此,您可以看到此结构效率低于Sequences,但如果您实际上不需要所有条目(例如稀疏图的表示,其中节点是整数),则提供更高的安全性和更大的好处.

为了完整性,我想提一个叫做的包persistent-vector,它实现了clojure风格的向量,但似乎被放弃了,因为最后一次上传来自(2012).

结论

所以对于你的用例,我强烈推荐,Data.Sequence或者Data.Vector不幸的是我对后者没有任何经验,所以你需要自己尝试一下.从我所知道的东西,它提供了一个称为流融合的强大功能,它优化了在一个紧密的"循环"中执行多个函数,而不是为每个函数运行循环.Vector可在此处找到教程.