问题描述
我正在ConcurrentSkipListSet上使用DescendingIterator方法.我刚刚检查了文档并注意到以下评论:
I’m using the descendingIterator method on ConcurrentSkipListSet. I’ve just checked the documentation and noticed the following comment:
升序视图及其迭代器比降序视图更快."
‘Ascending ordered views and their iterators are faster than descending ones.’
很遗憾，它没有提供任何更多信息.有什么样的性能差异?重要吗?为什么会有性能差异?
Unfortunately it doesn’t provide any more information on this. What kind of performance difference is there? is it significant? and why is there a performance difference?
推荐答案
如果您在Wikipedia页面上查找跳过列表，您会发现它们实际上是链接列表的一种复杂形式，其中的链接朝着列表条目的顺序排列. (该图清楚地说明了这一点...)
If you look at the Wikipedia page for Skip Lists you will see that they are effectively a complicated form of linked list with the links going in the direction of an ordering of the list entries. (The diagram illustrates this clearly ...)
在向前浏览跳过列表时，您只是在跟踪链接.每个next()调用都是一个O(1)操作.
When you traverse the skip list in the forward direction, you are simply following the links. Each next() call is an O(1) operation.
以相反的方向遍历跳过列表时，每个next()调用都必须在返回的最后一个键之前中找到键.这是一个O(logN)操作.
When you traverse the skip list in the reverse direction, each next() call has to find the key before the last key returned. This is an O(logN) operation.
(但是，向后遍历跳过列表比向后遍历单个链接列表要快得多.对于每个next()调用，这都是O(N)...)
(However, traversing a skip list backwards is still substantially faster than traversing a singly linked list backwards. That would be O(N) for each next() call ...)
如果您在引擎盖下看，您会发现ConcurrentSkipListSet实际上是ConcurrentSkipListMap的包装.在该类中，地图的跳过列表表示中的Node对象在升键方向上形成了单链.... (从前)得出结论，升序迭代比降序迭代快.
If you look under the hood, you will see that a ConcurrentSkipListSet is actually a wrapper for a ConcurrentSkipListMap. In that class, the Node objects in the skip list representation of the map form singly linked chains ... in the ascending key direction. It follows (from the previous) that ascending iteration is faster than descending iteration.
由于O(1)与O(logN)的差异，性能差异将非常显着，并且随着设置大小的增加，性能差异将变得更加显着.
The performance difference will be significant, and it will get more significant as the set size increases because of the O(1) versus O(logN) difference.
这篇关于为什么ConcurrentSkipListSet升序迭代器比降序迭代器“更快"?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！