具有排名操作的无锁跳跃列表
是否有人知道任何支持排名操作（即查找第 k 个元素）的无锁跳表实现和/或研究论文？或者，有人知道这种操作永远无法奏效的根本原因吗？
奖励点：
不假设垃圾收集的实现。根据我的经验，很多研究论文都忽略了内存管理。
支持：
有关如何在常规跳表中完成排序操作的说明：William Pugh 的“A Skip List Cookbook”
对于更好的无锁跳表描述之一：“实用无锁” ” 作者：Keir Fraser
更好的无锁跳表实现之一：http://www.1024cores.net/home/parallel-computing/concurrent-skip-list
Is anyone aware of any lock-free skiplist implimentations and/or research papers that support the rank operation (i.e. find kth element)? Alternatively, is anyone aware of a fundamental reason why such an operation could never work?
Bonus points:
An implimentation that does not assume garbage collection. It has been my experience quite a few research papers ignore memory management.
Support:
For a description of how the rank operation may be done in a regular skiplist: "A Skip List Cookbook" by William Pugh
For one of the better lock-free skiplist descriptions: "Practical lock-freedom" by Keir Fraser
One of the better lock-free skiplist implimentations: http://www.1024cores.net/home/parallel-computing/concurrent-skip-list
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
与key、value和level不同，它们是skiplist中元素的本地属性，不受其他元素操作的影响， >元素的排名，即它在列表中的位置，是随着插入和删除较低排名元素而改变的属性。因此，对于并发跳跃列表，元素的排名非常短暂，因为它可能会在任何时刻被并发运行的插入或删除较低排名元素的操作更改。
例如，假设您通过 1 级列表对第 k 个元素进行线性搜索。当您执行k步时，并发修改可能会添加或删除任意数量的先前元素，因此您刚刚找到的元素的当前排名实际上是未知的。此外，当线程执行 k 次前向迭代时，可以在其当前位置和开始搜索时的第 k 元素之间进行并发更改。因此，搜索最终得到的既不是当前排名为 k 的元素，也不是搜索开始时排名为 k 的元素。这只是一些随机元素！
简而言之，对于并发列表，元素的排名是一个不明确的概念，按排名搜索是一个不明确的操作。这是它永远无法工作的根本原因，也是实现者永远不应该费心提供此类操作的根本原因。
Unlike key, value and level, which are local properties of an element in a skiplist and are not affected by operations with other elements, rank of an element, i.e. its position in the list, is a property that changes with insertion and removal of elements with lower rank. Therefore, for a concurrent skiplist, rank of an element is very ephemeral because it may be changed in any moment by a concurrently running operation that inserts or delets a lower rank element.
For example, suppose you do linear search of k-th element through the level 1 list. At the moment you did k steps, concurrent modifications might add or remove any number of prior elements, so the current rank of the element you just find is in fact unknown. Moreover, while the thread is performing the k forward iterations, concurrent changes can be done between its current position and the element that was k-th when it started the search. So what the search ends up with is neither the element with the current rank of k nor the one that has the rank of k when the search started. It's just some random element!
To say it short, for concurrent list, rank of an element is an ill-defined concept and searching by rank is an ill-defined operation. This is the fundamental reason why it could never work, and why implementers should never bother with providing such operation.