1

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

复杂度怎么仍然是 O(lg n)？

4

2 回答 2

6

如果这能给你一个直觉，这里是一个带有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 指出了 Okasaki 在此类数据结构方面的出色工作（它被编辑为我绝对推荐的一本书，但前提是您真的对这个相当高级的主题感兴趣），其中实现了许多基于这些想法的数据结构。

但相反，其他一些结构很难以这种方式持久化。通常，数组是包含大量元素的非常扁平的结构。因此，如果您想返回数组的修改版本，您基本上必须对现有数组进行原地变异（丢失以前的版本，因此这不是持久的）或将整个数组复制到新版本（线性时间和内存成本） ）。前面的示例之所以有效，是因为有一些具有独立子结构（平衡树的子树，列表的尾部）的间接可以单独使用而无需复制；但是数组只是没有这种独立子结构的平面结构。但这可能是一个有趣的性能权衡：缺乏间接性正是数组访问是恒定时间的原因（在这里忘记缓存），O(log n)O(1)在实际实践中，它比数组小但明显更多）。

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

请注意，并非所有内容都丢失了：您可以提出此类数据结构的持久版本。你总是可以通过付出O(log n)代价来做到这一点（通过将你的可变内存表示为从整数到东西的持久平衡树），但在大多数情况下，你也可以很聪明，并提供比这更快的持久数据结构，希望只有一个比不关心持久性的对应物慢一点。涉及到各种权衡，但如果您的应用程序需要持久性（例如，您代表系统的状态，您需要经常为其状态快照，有时会回溯到早期版本），您会很高兴有这些替代方案.

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

于 2013-02-16T07:30:01.940 回答
6

以前的地图大部分都由新地图共享。只有一小部分不同。您可以在 Chris Okasaki 的论文Purely Functional Data Structures中阅读所有关于为什么不可变数据结构表现出色的信息。

于 2013-02-16T04:10:38.367 回答