纯函数并发跳表

Question

Pugh( Skip lists，1990)提供了具有对数时间操作的排序字典，如搜索树，但skip lists are much more amenable to concurrent updates。

有没有可能创建一个高效的纯功能并发跳跃列表？如果没有，是否有可能创建一种高效的、纯功能的并发排序字典？

Answer 1

跳过列表的属性使它们有利于并发更新(即大多数添加和减去是局部的)，也使它们不利于不可变性(即列表中的许多较早的项最终指向较晚的项，因此必须进行更改)。

具体来说，跳过列表由如下所示的结构组成：

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

现在，如果您有一个更新，比方说，删除了NODE2b或NODE1b，您可以在本地处理它:您只需分别将2a指向2c或将1a指向2a，就完成了。不幸的是，因为叶节点都指向另一个节点，所以对于函数式(不可变)更新来说，这不是一个好的结构。

因此，树结构更适合于不变性(因为损害总是局部有限的--只有您关心的节点和它的直接父节点向上延伸到树根)。

并发更新不能很好地处理不可变的数据结构。如果你仔细想想，任何函数式解决方案都会将A更新为f(A)。如果你想要两个更新，一个是由f提供的，另一个是由g提供的，你几乎必须执行f(g(A))或g(f(A))，或者你必须拦截请求并创建一个新的操作h = f,g，你可以一次性应用它(或者你必须做各种其他非常聪明的事情)。

然而，并发读取在不可变的数据结构中工作得非常好，因为可以保证不会有任何状态变化。如果你不认为你可以有一个读/写循环，在任何其他写操作中断之前解决，那么你永远不需要锁定读操作。

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

Answer 2

Andrew McKinlay的解决方案是真正的跳过列表的真正的“真正的”函数解决方案，但它也有缺点。你需要花费对数时间来访问一个元素，但是现在在head元素之外的变异变得无望了。你想要的答案隐藏在无数的路径副本中！

我们能做得更好吗？

部分问题是，从-infinity到您的项目有多个路径。

但是，如果你仔细考虑过搜索跳过列表的算法，你就永远不会使用这个事实。

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

现在，我们可以将“手指”的概念考虑到数据结构中，这是一种函数式技术，使您能够专注于一个特定的元素，并提供一条返回根的路径。

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

-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

从那里可以删除8，按下手指在其他地方，您可以继续使用手指在结构中导航。

从这个角度看，我们可以看到跳过列表中的特权路径形成了一个生成树！

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

所有操作保持为O(log )，您可以照常使用随机化的跳表结构或确定性的跳表结构。

也就是说，当我们将跳过列表分解成一个首选路径的概念时，我们就会得到一个跳过列表只是一棵树，其中包含一些我们在插入/搜索/删除时不需要的冗余的非首选链接，这样从右上角开始的每条路径的长度都是O(log )，这取决于您的更新策略。

即使没有finger，您也可以使用这种形式在树中保持每次插入/删除/更新的O(log )预期时间。

现在，你的问题中没有意义的关键字是“并发”。纯函数式数据结构没有就地突变的概念。你总是能创造出新的东西。从某种意义上说，并发函数更新是很容易的。每个人都有自己的答案！他们就是看不到对方。

Answer 3

不是跳过列表，但似乎与问题描述相匹配: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使用单词的意义上是“持久的”(不可变的，并且能够在构造更新版本时保持其性能保证)。

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