纯函数并发跳过列表

跳过列表的特性使其有利于并发更新(即大多数加减是本地的),也使其不利于不变性(即列表中的许多早期项最终指向后面的项,并且必须进行更改)。

具体来说,跳过列表由如下结构组成:

NODE1 ---------------------> NODE2 ---------...
  |                           |
  V                           V
NODE1a --> NODE1b ---------> NODE2a --> NODE2b --> NODE2c --- ...

现在,如果你有一个更新,比如说,删除 NODE2b 或 NODE1b ,你可以很局部地处理它:你只要指向 2a 到 2c 或 1a 到 你就完了。不幸的是,因为叶节点都指向另一个,所以对于函数(不可变)更新来说,它不是一个好的结构。

因此,树结构更适合于不变性(因为损坏总是局部受限的——只是您所关心的节点和它的直接父节点通过树的根向上)。

A 作为 f(A) . 如果你想要两个更新,一个由 f 一个是 g ,你必须要做的 f(g(A)) 或 g(f(A)) ,或者您必须截获请求并创建新操作 h = f,g 你可以一次性申请(或者你必须做其他各种非常聪明的事情)。

因此,写重数据结构可能更好地以可变方式实现(使用类似于跳过列表的方法,您只需要在本地锁定),而读重数据结构可能更好地以不变方式实现(其中树是更自然的数据结构)。

Andrew McKinlay的解决方案是真正的“真正的”函数式解决方案,但是它有一个缺点。您需要花费对数时间来访问一个元素,但是现在超出head元素的突变变得毫无希望。你想要的答案埋在无数的路径副本里!

我们能做得更好吗?

但是如果你仔细考虑一下搜索技巧专家的算法,你永远不会使用这个事实。

我们可以认为树中的每个节点都有一个首选链接,从左边到它的最上面的链接,在某种意义上可以认为是“拥有”该条目。

现在我们可以从一个简单的跳过列表开始

-inf-------------------> 16
-inf ------> 8 --------> 16
-inf -> 4 -> 8 -> 12 --> 16

逐级扩展:

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8 --------> 16
  |          |            |
  v          v            v
-inf -> 4 -> 8 -> 12 --> 16

-inf-------------------> 16
  |                       |
  v                       v
-inf ------> 8           16
  |          |            |
  v          v            v
-inf -> 4    8 -> 12     16

然后,你可以移动一个“手指”到位置8跟踪所有的指针,你必须翻转到那里。

-inf ------------------> 16
   ^                      |
   |                      v
-inf <------ 8           16
   |         |            |
   v         v            v
-inf -> 4    8 -> 12     16

这样看,我们可以看到跳过列表中的特权路径形成了一个生成树!

如果在树中只有特权指针并且使用这样的“瘦节点”,那么用手指移动一步就是一个O(1)操作。如果使用脂肪节点,那么手指向左/向右移动可能会更昂贵。

所有操作都保持O(logn),您可以像往常一样使用随机跳过列表结构或确定性跳过列表结构。

不是跳过列表,但似乎与问题描述相符:Clojure的持久红黑树(参见 PersistentTreeMap.java ). 来源包含以下通知:

/**
 * Persistent Red Black Tree
 * Note that instances of this class are constant values
 * i.e. add/remove etc return new values
 * <p/>
 * See Okasaki, Kahrs, Larsen et al
 */

这些树保持元素的顺序,并且在Rich Hickey使用这个词的意义上是“持久的”(不可变的,并且能够在构建更新版本时保持它们的性能保证)。

如果您想使用它们,可以使用函数在Clojure代码中构造实例 sorted-map .

如果您只需要在跳过列表的前面添加cons,那么应该可以创建一个持久不变的版本。