我的理解是，它们并不是二叉树（例如红黑树）的有用替代品，而是数据库使用中的 B 树，因此您可以将级别数保持在可行的最小值，并处理基于 K 的日志而不是基于 2 的日志以获得性能特征。 概率跳跃列表的算法（恕我直言）比相应的 B 树算法更容易正确。 另外还有一些关于无锁跳过列表的文献。 几个月前我考虑过使用它们，但后来放弃了发现 HDF5 库的努力。
My understanding is that they're not so much a useful alternative to binary trees (e.g. red-black trees) as they are to B-trees for database use, so that you can keep the # of levels down to a feasible minimum and deal w/ base-K logs rather than base-2 logs for performance characteristics. The algorithms for probabilistic skip-lists are (IMHO) easier to get right than the corresponding B-tree algorithms. Plus there's some literature on lock-free skip lists. I looked at using them a few months ago but then abandoned the effort on discovering the HDF5 library.
Actually, for one of my projects, I am implementing my own full STL. And I used a skiplist to implement my std::map. The reason I went with it is that it is a simple algorithm which is very close to the performance of a balanced tree but has much simpler iteration capabilities.
Also, Qt4's QMap was a skiplist as well which was the original inspiration for my using it in my std::map.
Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:
Java 1.6 (Java SE 6) introduced ConcurrentSkipListSet and ConcurrentSkipListMap to the collections framework. So, I'd speculate that someone out there is really using them.
Skiplists tend to offer far less contention for locks in a multithreaded situation, and (probabilistically) have performance characteristics similar to trees.
I implemented a variant that I termed a Reverse Skip List for a rules engine a few years ago. Much the same, but the reference links run backward from the last element.
This is because it was faster for inserting sorted items that were most likely towards the back-end of the collection.
It was written in C# and took a few iterations to get working successfully.
The skip list has the same logarithmic time bounds for searching as is achieved by the binary search algorithm, yet it extends that performance to update methods when inserting or deleting entries. Nevertheless, the bounds are expected for the skip list, while binary search of a sorted table has a worst-case bound.
Skip Lists are easy to implement. But, adjusting the pointers on a skip list in case of insertion and deletion you have to be careful. Have not used this in a real program but, have doen some runtime profiling. Skip lists are different from search trees. The similarity is that, it gives average log(n) for a period of dictionary operations just like the splay tree. It is better than an unbalanced search tree but is not better than a balanced tree.
Every skip list node has forward pointers which represent the current->next() connections to the different levels of the skip list. Typically this level is bounded at a maximum of ln(N). So if N = 1million the level is 13. There will be that much pointers and in Java this means twie the number of pointers for implementing reference data types. where as a balanced search tree has less and it gives same runtime!!.
SkipList Vs Splay Tree Vs Hash As profiled for dictionary look up ops a lock stripped hashtable will give result in under 0.010 ms where as a splay tree gives ~ 1 ms and skip list ~720ms.
发布评论
评论（7）
我的理解是，它们并不是二叉树（例如红黑树）的有用替代品，而是数据库使用中的 B 树，因此您可以将级别数保持在可行的最小值，并处理基于 K 的日志而不是基于 2 的日志以获得性能特征。 概率跳跃列表的算法（恕我直言）比相应的 B 树算法更容易正确。 另外还有一些关于无锁跳过列表的文献。 几个月前我考虑过使用它们，但后来放弃了发现 HDF5 库的努力。
有关该主题的文献：
Bill Pugh 的论文：
非学术论文/教程：
My understanding is that they're not so much a useful alternative to binary trees (e.g. red-black trees) as they are to B-trees for database use, so that you can keep the # of levels down to a feasible minimum and deal w/ base-K logs rather than base-2 logs for performance characteristics. The algorithms for probabilistic skip-lists are (IMHO) easier to get right than the corresponding B-tree algorithms. Plus there's some literature on lock-free skip lists. I looked at using them a few months ago but then abandoned the effort on discovering the HDF5 library.
literature on the subject:
Papers by Bill Pugh:
non-academic papers/tutorials:
实际上，对于我的一个项目，我正在实现我自己的完整 STL。 我使用了一个跳过列表来实现我的
std::map。 我选择它的原因是它是一个简单的算法，非常接近平衡树的性能，但具有更简单的迭代功能。另外，Qt4 的 QMap 也是一个跳过列表，这也是我使用它的最初灵感在我的
std::map中。Actually, for one of my projects, I am implementing my own full STL. And I used a skiplist to implement my
std::map. The reason I went with it is that it is a simple algorithm which is very close to the performance of a balanced tree but has much simpler iteration capabilities.Also, Qt4's QMap was a skiplist as well which was the original inspiration for my using it in my
std::map.几年前，我为概率算法类实现了自己的算法。 我不知道有任何库实现，但已经很长时间了。 实施起来非常简单。 我记得它们对于大型数据集有一些非常好的特性，并且避免了一些重新平衡的问题。 我认为实现也比一般的二进制尝试更简单。 这里有一个很好的讨论和一些示例 C++ 代码：
http://www.ddj。 us/cpp/184403579?pgno=1
还有一个带有运行演示的小程序。 可爱的 90 年代 Java 辉煌在这里：
http://www.geocities.com/siliconvalley/网络/1854/skiplist.html
Years ago I implemented my own for a probabilistic algorithms class. I'm not aware of any library implementations, but it's been a long time. It is pretty simple to implement. As I recall they had some really nice properties for large data sets and avoided some of the problems of rebalancing. I think the implementation is also simpler than binary tries in general. There is a nice discussion and some sample c++ code here:
http://www.ddj.us/cpp/184403579?pgno=1
There's also an applet with a running demonstration. Cute 90's Java shininess here:
http://www.geocities.com/siliconvalley/network/1854/skiplist.html
Java 1.6 (Java SE 6) 引入了 ConcurrentSkipListSet< /a> 和 ConcurrentSkipListMap 到集合框架。 所以，我推测有人真的在使用它们。
在多线程情况下，跳表往往会提供更少的锁争用，并且（概率上）具有与树类似的性能特征。
请参阅 William Pugh 的原始论文 [pdf] 。
Java 1.6 (Java SE 6) introduced ConcurrentSkipListSet and ConcurrentSkipListMap to the collections framework. So, I'd speculate that someone out there is really using them.
Skiplists tend to offer far less contention for locks in a multithreaded situation, and (probabilistically) have performance characteristics similar to trees.
See the original paper [pdf] by William Pugh.
几年前，我实现了一个变体，将其称为规则引擎的反向跳过列表。 大致相同，但参考链接从最后一个元素向后延伸。
这是因为插入最有可能朝向集合后端的已排序项目的速度更快。
它是用 C# 编写的，经过几次迭代才成功运行。
I implemented a variant that I termed a Reverse Skip List for a rules engine a few years ago. Much the same, but the reference links run backward from the last element.
This is because it was faster for inserting sorted items that were most likely towards the back-end of the collection.
It was written in C# and took a few iterations to get working successfully.
跳跃列表具有与二分搜索算法相同的搜索对数时间范围，但它将该性能扩展到插入或删除条目时更新方法。 然而，跳跃列表的界限是预期的，而排序表的二分搜索有最坏情况的界限。
The skip list has the same logarithmic time bounds for searching as is achieved by the binary search algorithm, yet it extends that performance to update methods when inserting or deleting entries. Nevertheless, the bounds are expected for the skip list, while binary search of a sorted table has a worst-case bound.
跳过列表很容易实现。 但是，在插入和删除时调整跳跃列表上的指针时必须小心。 尚未在实际程序中使用此功能，但已进行了一些运行时分析。 跳过列表与搜索树不同。 相似之处在于，它就像展开树一样给出一段字典操作的平均log(n)。 它比不平衡搜索树好，但并不比平衡树好。
每个跳表节点都有前向指针，它们表示到跳表不同级别的 current->next() 连接。 通常，该水平的最大值为 ln(N)。 因此，如果 N = 100 万，则级别为 13。将会有那么多的指针，在 Java 中，这意味着用于实现引用数据类型的指针数量增加一倍。 作为平衡搜索树，它的运行时间更少，但运行时间相同！
SkipList 与展开树与哈希针对字典查找操作进行分析，锁剥离哈希表将在 0.010 毫秒内给出结果，而展开树给出 ~ 1 毫秒和跳跃列表 ~ 720 毫秒。
Skip Lists are easy to implement. But, adjusting the pointers on a skip list in case of insertion and deletion you have to be careful. Have not used this in a real program but, have doen some runtime profiling. Skip lists are different from search trees. The similarity is that, it gives average log(n) for a period of dictionary operations just like the splay tree. It is better than an unbalanced search tree but is not better than a balanced tree.
Every skip list node has forward pointers which represent the current->next() connections to the different levels of the skip list. Typically this level is bounded at a maximum of ln(N). So if N = 1million the level is 13. There will be that much pointers and in Java this means twie the number of pointers for implementing reference data types. where as a balanced search tree has less and it gives same runtime!!.
SkipList Vs Splay Tree Vs Hash As profiled for dictionary look up ops a lock stripped hashtable will give result in under 0.010 ms where as a splay tree gives ~ 1 ms and skip list ~720ms.