26

跳过列表（Pugh，1990）为排序字典提供了对数时间操作，如搜索树，但跳过列表更适合并发更新。

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

4

4 回答 4

39

跳过列表的特性使它们有利于并发更新（即大多数加法和减法都是局部的）也使它们不利于不变性（即列表中的许多早期项目最终指向后面的项目，并且必须被改变）。

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

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

现在，如果您有一个更新，例如删除NODE2bor NODE1b，您可以在本地处理它：您只需分别指向2aor2c就1a可以2a了。不幸的是，因为叶子节点都指向另一个，所以对于功能性（不可变）更新来说，这不是一个好的结构。

因此，树结构更适合不变性（因为损坏总是局部受限的——只是您关心的节点及其直接父节点通过树的根部）。

并发更新不适用于不可变数据结构。如果您考虑一下，任何功能解决方案都有Aas的更新f(A)。如果您想要两个更新，一个由给出，一个f由非常聪明的东西）。gf(g(A))g(f(A))h = f,g

但是，并发读取在不可变数据结构中工作得非常好，因为您可以保证没有状态更改。如果您不假设您可以在任何其他写入中断之前解决读/写循环，那么您永远不必锁定读取。

因此，写入繁重的数据结构可能更好地实现可变（并且使用类似跳过列表的东西，您只需要在本地锁定），而读取繁重的数据结构可能更好地实现不可变（树是更自然的数据结构）。

于 2010-08-15T23:53:42.480 回答
17

Andrew McKinlay 的解决方案是这里真正的跳过列表的真正“真正”功能解决方案，但它有一个缺点。您花费对数时间来访问一个元素，但现在超出头部元素的突变变得毫无希望。你想要的答案被埋没在无数的路径副本中！

我们能做得更好吗？

部分问题在于从 -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 n)，您可以像往常一样使用随机跳过列表结构或确定性结构。

也就是说，当我们将跳过列表分解为首选路径的概念时，我们会得到跳过列表只是一棵树，其中包含一些我们不需要插入/搜索/删除的冗余非首选链接，因此从右上角开始，每条路径的长度为 O(log n) ，概率很高或有保证，具体取决于您的更新策略。

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

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

于 2015-08-28T01:04:42.270 回答
6

不是跳过列表，但似乎与问题描述相匹配：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。

于 2010-08-15T23:18:58.463 回答
4

如果您只需要在跳过列表的前面进行 cons，那么应该可以制作一个持久不可变的版本。

这种跳过列表的优点是“随机”访问。例如，您可以比在常规单链表中更快地访问第 n 个元素。

于 2011-04-05T16:39:24.123 回答