问题标签 [skip-lists]

我已经使用基于http://www.boyet.com/articles/LockfreeQueue.html的比较和交换在 C 中实现了一个无锁队列。

它工作得很好，但我正在尝试将此队列集成到我已经实现的无锁跳过列表中。我将跳过列表用作优先级队列，并希望在发生优先级冲突时使用每个节点内的无锁队列来存储多个值。但是，由于当我检测到优先级冲突时在跳过列表中管理节点的方式，我需要能够仅当队列不为空时才能将项目添加到队列中。

由于队列的无锁特性，我不确定如何实际执行此操作。

所以基本上我将如何编写一个原子 enqueue_if_not_empty 操作？

如何在时间复杂度（最坏情况）中将 2 个给定Skip lists（每个都有 n 个键）合并为一个？Skip ListO(n)

只是寻找算法 - 没有特定的实现/语言。

我有兴趣实现一个优先级队列以启用一个也相对简单的高效 Astar 实现（我的意思是优先级队列很简单）。

似乎因为跳过列表提供了一个简单的 O(1) 提取最小操作和一个 O(Log N) 的插入操作，它可能与更难实现的具有 O(log N) 提取的斐波那契堆竞争 - Min 和 O(1) 插入。我认为 Skip-List 对于节点稀疏的图会更好，而斐波那契堆对于节点更密集的环境会更好。

这可能会使斐波那契堆通常更好，但我是否正确假设 Big-Oh 明智的这些将是相似的？

我ConcurrentSkipListSet在 Java Collection Framework 中找到，它由一个跳过列表备份。但是Java中有跳过列表吗？一套在我的用例中不起作用。我需要一个支持重复的可索引列表。

ZADD的 redis文档指出该操作为 O(log N )。

但是，当插入的元素位于排序顺序的开头或结尾时，有谁知道 ZADD 是否比 O(log N ) 好？

例如，对于某些实现，这可能是 O(1)。

具体来说，redis教程指出：

排序集是通过包含跳过列表和哈希表的双端口数据结构实现的，因此每次添加元素时，Redis 都会执行 O(log( N )) 操作。

修改跳过列表以支持在开头和结尾插入O( k )似乎是合理的，其中k是跳过列表的最大级别。

我有skiplist的实现，但它告诉我非常不清楚的错误

错误说包含不是skipset结构的功能，有些；未命中等，请查看错误列表

是否有人知道任何支持排名操作（即找到第 k 个元素）的无锁跳过列表实现和/或研究论文？或者，有没有人知道为什么这样的操作永远行不通的根本原因？

奖励积分：

不假设垃圾收集的实施。根据我的经验，很多研究论文都忽略了内存管理。

支持：

有关如何在常规跳过列表中完成排名操作的描述：William Pugh 的“跳过列表食谱”

对于更好的无锁跳过列表描述之一：Keir Fraser 的“Practical lock-freedom”

更好的无锁跳过列表实现之一： http ://www.1024cores.net/home/parallel-computing/concurrent-skip-list

有大量关于无锁双向链表的研究。同样，在无锁跳过列表上也有大量研究。然而，据我所知，没有人管理过无锁的双向链接跳过列表。有没有人知道任何相反的研究，或者是这种情况的原因？

编辑：特定场景是用于构建快速分位数（50%、75% 等）累加器。样本在 O(log n) 时间内被插入到跳过列表中。通过维护当前分位数的迭代器，我们可以在 O(1) 时间内将插入的值与当前分位数进行比较，并且可以轻松确定插入的值是在分位数的左侧还是右侧，以及分位数的多少结果需要移动。左移需要前一个指针。

据我了解，面对同时插入和删除的多个线程，任何困难都来自保持先前的指针一致。我想这个解决方案几乎肯定会巧妙地使用指针标记。

在这样的跳过列表中：

元素 4 是否可以访问第二个和第三个列表中的自身？我问的原因是因为我试图弄清楚如何为跳过列表实现删除操作。谢谢

我正在尝试找到最佳算法

.

an 的定义ideal skip list是在第一级我们将拥有所有元素，在一半以上的级别，在四分之一之后的那个......等等。

我正在考虑O(n)运行时，其中涉及为原始链接列表中的每个节点投掷硬币，无论是否针对特定节点，我是否应该上去，并为楼上的当前节点创建另一个重复节点.. . 最终这个算法会产生 O(n) ，有没有更好的算法？

问候