我在ConcurrentSkipListSet上使用descendingIterator方法。我刚刚查看了文档,并注意到以下注释:
‘升序视图及其迭代器比降序视图更快。’
不幸的是,它没有提供更多关于这方面的信息。有什么样的性能差异?它有意义吗?为什么会有性能上的差异?
发布于 2018-06-07 21:57:16
除了Stephen的回答之外,我还写了一个简单的基准测试:
@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));
}
}
}
Main方法:
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
repository的代码示例,它在升序迭代器和降序迭代器中使用:
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
可视化性能差异:
https://stackoverflow.com/questions/50738555
复制相似问题