高效修改持久化数据结构的方法

Question

我理解通常树结构用于修改持久化数据结构（创建新节点并替换所有祖先节点）。

但是如果我有一个包含数万个节点的树，我需要修改其中数千个节点，我不想逐个创建数千个新根节点，我只需要一个由同时修改所有节点而产生的新根节点。

例如： 以持久化二叉树为例。在单个更新节点的情况下，它会搜索直到找到节点，创建一个带有修改和旧子节点的新节点，并创建新的祖先节点直到根节点。

在批量更新的情况下，我们可以这样做: 不仅更新单个节点，而是一次性更新1000个节点。

在根节点处，当前列表是完整列表。然后将该列表分成与左节点匹配和与右节点匹配的部分。如果没有匹配到其中一个子节点，则不要向其下降。然后向左节点下降（假设有匹配项），将其搜索列表分成其子节点，并继续进行。当您有一个单独的节点和匹配项时，您会更新它并返回，根据需要替换和更新祖先和其他分支。

这将导致只有一个新根节点，即使它修改了任意数量的节点。

- mentics

Answer 1

这种“大规模修改”操作有时被称为批量更新。当然，具体情况取决于您正在处理哪种数据结构以及您正在尝试执行哪种修改。

典型的操作可能包括“删除所有满足某些条件的值”或“增加与此列表中所有键相关联的值”。通常，可以在对整个结构进行单次遍历时完成这些操作，时间复杂度为O(n)。

您似乎关心创建“数千个新根”的内存分配问题。按顺序执行每个操作的典型分配为O(k log n)，其中k是要修改的节点数。执行整个结构的单次遍历的典型分配为O(n)。哪个更好取决于k和n。

在某些情况下，可以通过特别关注何时发生更改来减少分配的数量，但这需要更复杂的代码。例如，如果您有一个返回树的递归算法，则可以修改该算法以返回一个带有指示是否发生更改的布尔值的树。然后算法可以在分配新节点之前检查这些布尔值，以查看旧节点是否可以安全地重用。但是，除非他们有证据表明额外的内存分配实际上是一个问题，否则人们通常不会费心进行额外的检查。

- Chris Okasaki

---

感谢提供这些有用的信息。我之前没有考虑过在整个结构上进行遍历。我已经在问题中添加了一个例子。对我来说，这个例子的内存占用比逐一遍历要小得多。在每个分支处拆分列表后，搜索可能类似于 O(k log n)，但更新每个节点（包括祖先节点）只需要更新一次。对于逐一遍历的情况来说：每个节点的搜索需要 O(k log n) 的时间，但然后为更新祖先节点（某些重复的节点）需要另外 (k * avg depth) 的时间。在问题的例子中，这样做能显著减少时间吗？ - mentics

当然，你的新二叉树示例本质上就是我所说的遍历整个结构，因为通常它会向树的两侧进行递归调用。当然，在特殊情况下，您可能能够提前停止并避免遍历树的某些部分。在其他情况下，您可能仍然需要遍历树的一部分，只是发现该部分树实际上没有发生任何更改。这就是我提到的额外布尔返回值可能有用的地方，如果您想避免不必要的分配。 - Chris Okasaki

只有在需要更新与该分支匹配的节点时，您才会沿着该分支走。它的搜索方式与逐个搜索的情况完全相同，但它同时执行所有k次搜索。因此，您永远不需要返回关于是否已更新的布尔值，因为除非需要更新，否则您不会一开始就沿着该分支走。 - mentics

如果你能通过查看特定节点来确定在该节点或其任何后代中都不需要执行任何操作，那么你根本不需要进入该节点。然而，通常情况下，你可能会发现在节点本身不需要执行任何操作，但不一定知道其后代的情况，在这种情况下，你可能仍需要遍历到后代节点。 - Chris Okasaki

考虑到我们正在讨论与O(k log n)情况的比较，我假设我们正在谈论相同类型的操作，这意味着我们将确切地知道如何搜索和何时停止。如果您不知道后代的情况通常需要进行详尽的搜索，因此这与我的问题无关。在这个批量更新问题中，我们有一个现有节点列表，我们要么想删除它们，要么修改它们的字段，或以某种方式用更新的值替换它们。 - mentics

Clojure通过提供其许多集合的*瞬态(transient)*版本来解决这个问题。这是一个临时的、仅本地的、可变版本的持久化集合，它允许进行一批操作，最小化节点的分配和复制。当完成一批操作后，在将实例释放给“公众”之前，它会被转换回不可变的持久化集合。从瞬态到持久化的转换是常数时间的。您可以在这里阅读更多关于它们的信息http://clojure.org/transients - Chouser

Answer 2

您所寻找的实现方法可以在Clojure（和ClojureScript）的transients中找到。

简而言之，给定一个完全不可变的持久化数据结构，它的瞬态版本将使用破坏性（分配高效）突变进行更改，当您完成对性能敏感的操作后，您可以将其转换回适当的持久化数据结构。 只有在转换回持久化数据结构时才会创建新的根（例如），从而将相关成本摊销到您在其瞬态形式下执行的逻辑操作数量上。

- cemerick