关于OCaml中Map.remove的复杂度

Question

看起来

Map.remove

会返回一个新的地图结构，而原始地图保持不变。

复杂度怎么可能还是O(lg n)？

Answer 1

新地图共享了大部分旧地图。只有一小部分不同。您可以在 Chris Okasaki 的论文纯函数式数据结构中阅读有关为什么不可变数据结构表现出奇出色的所有信息。

Answer 2

如果这能给你一个直觉，这里是堆栈的实现 使用

O(1)

Stack.pop，返回一个新的结构，保持 前一个不变（看看我如何弹出

test

两次）。

type 'a stack = Stack of 'a list
let empty = Stack []
let push x (Stack xs) = Stack (x :: xs)
let pop = function
  | Stack [] -> raise Not_found
  | Stack (x::xs) -> x, Stack xs


(* testing the structure in the toplevel *)

# let test = push 1 (push 2 (push 3 empty));;
val test : int stack = Stack [1; 2; 3]
# let (n, test2) = pop test;;
val n : int = 1
val test2 : int stack = Stack [2; 3]
# pop test2;;
- : int * int stack = (2, Stack [3])
# (* but the starting stack 'test' is still available *)
  pop test;;
- : int * int stack = (1, Stack [2; 3])

为什么有些结构是功能性的，而另一些结构是命令性的？

这可以归结为算法问题。有所谓的“纯功能数据结构”，它具有这样的属性，您可以以这样的方式实现您想要的操作，即大多数数据可以在结构的不同副本之间共享 - 请注意，这主要依赖于别名，如果这些结构的元素是可变的，那么这将是可观察的。

在

list

示例中，获取列表的尾部会得到一个不同的列表，该列表也是前一个列表的一部分，因此不涉及数据副本。对于

Map.remove

（或其他地图修改操作），您通常会修改从平衡树的根到您感兴趣的节点的路径，因此该路径（对数高度）在两种结构中会有所不同，但是树的其余部分，即沿着该路径的左子树和右子树，将不会被修改并且可以在两个结构之间共享，从而导致仅对数内存分配。

Jeffrey 指出冈崎在此类数据结构方面的出色工作（我绝对推荐将其编辑为一本书，但前提是你真的对这个相当高级的主题感兴趣），其中实现了许多基于这些想法的数据结构.

但相反，其他一些结构却很难通过这种方式持久化。通常，数组是包含大量元素的非常扁平的结构。因此，如果你想返回数组的修改版本，你基本上必须要么就地改变现有数组（丢失以前的版本，所以这不是持久的），要么将整个数组复制到新版本（线性时间和内存成本） ）。前面的示例之所以有效，是因为有一些具有独立子结构（平衡树的子树、列表尾部）的间接寻址可以单独使用而无需复制；但数组只是平面结构，没有这样的独立子结构。但这可能是一个有趣的性能权衡：缺乏间接性正是数组访问是恒定时间的原因（这里忘记缓存），而平衡树中的查找成本更高（

O(log n)

很小，但明显大于实际应用中数组的

O(1)

）。

哈希表可变的原因是它们是在数组之上实现的。哈希表是一个“存储桶”数组（以列表的形式实现，或者，如果您明智的话，可以是树数据结构），其中每个存储桶包含哈希到数组中相同键的所有元素。更新哈希表意味着更新存储桶（可以通过持久化方式完成），但是随后您需要更新数组，并且这是非持久化的，原因与上面相同。

请注意，并非所有内容都会丢失：您可以想出此类数据结构的持久版本。你总是可以通过支付

O(log n)

成本来做到这一点（通过将你的可变内存表示为从整数到东西的持久平衡树），但在大多数情况下，你也可以聪明地使用比这更快的持久数据结构，希望只比不关心持久性的对手慢一点。这涉及到各种权衡，但如果您应用需要持久性（例如，您正在代表一个系统的状态，您需要经常对其状态进行快照，并且有时回溯到早期版本），您会很高兴拥有这些周围的替代品。 在这方面，请参阅

关于持久数组的讨论

，以及这篇博客文章，了解 HAMT 的 OCaml 实现，HAMT 是一种著名的受哈希表启发的持久数据结构，受到 Clojure 社区的启发（Clojure 是一种专注于并发性并因此明智地避免可变状态，在持久数据结构领域产生了一些相当有趣的工作）。

Answer 3