data-structures - 实现不可变的、可增长的向量

Question

我有兴趣在 F# 中实现持久（例如纯函数式、不可变等）、可增长的向量，以便它们可以在 .NET 框架中使用。我当前的实现是 Hash-Mapped Trie 的一个变体，是根据Clojure 的 implementation完成的。

我在使用此实现实现随机访问插入和删除（在随机索引处插入和删除元素）时遇到问题。是否有一些算法/修改可以有效地进行这些操作，或者我可以查看其他一些实现？

澄清：当我说“插入”和“删除”时，我的意思是，例如，给定列表[1; 2; 3; 4]，插入500in position1会给我[1:500:2:3:4]。我不是指set或associate操作。

score 3 · Accepted Answer

3

手指树可能是您正在寻找的。有一个Clojure 实现可用。

于 2012-09-26T15:13:15.667 回答

score 1 · Accepted Answer

不可变向量/列表通常通过仅允许在一端插入然后在另一端共享不可变数据来提供快速更新。如果您想做非头/尾插入，那么您实际上想要做的是改变集合的不可变末端。您必须在要插入的项目周围拆分向量，然后将其重新拼接在一起以创建一个新向量，并且您能够做到的最好的时间是O(n)时间。

不可变排序树的工作方式略有不同，但它们也不会让您在少于O(n)的时间内重新编号索引（键）。

基本上，如果有人发现了一种在不可变向量中支持随机访问插入的有效方法，那么主流函数式语言之一就会支持它——但是没有这样的已知数据结构或算法，所以没有这样的实现。

score 1 · Accepted Answer

唯一能做的就是拆分和加入。这对于 clojure 向量非常无效。这就是为什么 Phill Bagwell 实现了一个可以在 log(n) 中拆分和连接的持久向量。

或直接阅读他的论文：infoscience.epfl.ch/record/169879/files/RMTrees.pdf

score 0 · Accepted Answer

0

移植 Haskell HAMT库？插入操作为O(log n )

于 2012-09-26T17:07:55.130 回答

4 回答 4