纯功能并发跳过列表

Question

跳过列表(Pugh,1990)提供了具有对数时间操作的排序字典,如搜索树,但跳过列表更适合并发更新.

是否有可能创建一个有效的纯功能并发跳过列表？如果没有,是否有可能创建任何类型的高效纯函数并发排序字典？

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到您的项目有多条路径.

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

我们可以认为树中的每个节点都有一个首选链接,它是从左边开始的最顶层链接,在某种意义上可以被认为是"拥有"该条目.

现在我们可以将"finger"的概念考虑到数据结构中,这是一种功能性技术,使您能够专注于一个特定元素,并提供返回根的路径.

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

-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)预期时间.

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

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使用单词的意义上是"持久的"(不可变并且能够在构造更新版本时保持其性能保证).

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