为什么 ConcurrentSkipListSet 上升迭代器比下降迭代器“更快”？
2022-09-03 07:04:45
我在 ConcurrentSkipListSet 上使用降序迭代器方法。我刚刚检查了文档，并注意到以下评论：
“升序有序视图及其迭代器比降序视图更快。
不幸的是，它没有提供有关此的更多信息。有什么样的性能差异？它很重要吗？为什么会有性能差异？
答案 1
如果你看一下维基百科页面的跳过列表，你会发现它们实际上是一种复杂的链接列表形式，链接朝着列表条目排序的方向发展。（该图清楚地说明了这一点...）
当您向前遍历跳过列表时，您只需按照链接进行操作即可。每个调用都是一个 O（1） 操作。next()
当您以相反方向遍历跳过列表时，每个调用都必须在最后一个密钥返回之前找到该密钥。这是一个 O（logN） 操作。next()
（但是，向后遍历跳过列表仍然比向后遍历单链列表快得多。这将是每个调用的O（N）...next()
如果你看一下引擎盖，你会看到 a 实际上是 一个 .在该类中，跳过列表中的对象表示的地图形式是单链接链...在上升的关键方向。由上一个可以看出，升序迭代比降序迭代更快。ConcurrentSkipListSetConcurrentSkipListMapNode
性能差异将是显著的，并且由于 O（1） 和 O（logN） 的差异，随着集合大小的增加，性能差异将变得更加显著。
答案 2
除了Stephen的答案之外，我还写了一个简单的Benchmark：
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
public class ConcurrentSkipListSetIteratorTest {
@Fork(1)
@Benchmark
public void ascItr(SetupParams params) {
Iterator<Integer> itr = params.cslset.iterator();
while (itr.hasNext()) itr.next();
}
@Fork(1)
@Benchmark
public void dscItr(SetupParams params) {
Iterator<Integer> itr = params.cslset.descendingIterator();
while (itr.hasNext()) itr.next();
}
@State(Scope.Benchmark)
public static class SetupParams {
private ConcurrentSkipListSet<Integer> cslset;
@Setup(Level.Invocation)
public void setUp() {
cslset = new SplittableRandom()
.ints(100_000, 0, 100_000)
.boxed()
.collect(Collectors.toCollection(ConcurrentSkipListSet::new));
}
}
}
主要方法：
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(ConcurrentSkipListSetIteratorTest.class.getSimpleName())
.jvmArgs("-ea", "-Xms512m", "-Xmx1024m")
.shouldFailOnError(true)
.build();
new Runner(opt).run();
}
此外，下面是存储库中的一个代码示例，用于适当地升序和降序迭代器：JDK 10
private void ascend() {
...
for (;;) {
// there is a link to the next node
next = next.next; // O(1) operation
...
}
}
private void descend() {
...
for (;;) {
// but, there is no link to the previous node
next = m.findNear(lastReturned.key, LT, cmp); // O(logN) operation
...
}
}
元素的最终结果：10_000
Benchmark Mode Cnt Score Error Units
ascItr avgt 5 0,075 ± 0,029 ms/op
dscItr avgt 5 0,810 ± 0,116 ms/op
对于元素：100_000
Benchmark Mode Cnt Score Error Units
ascItr avgt 5 2,764 ± 1,160 ms/op
dscItr avgt 5 11,110 ± 0,937 ms/op
可视化性能差异：
推荐
