首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >为什么ConcurrentSkipListSet升序迭代器比降序迭代器“快”?

为什么ConcurrentSkipListSet升序迭代器比降序迭代器“快”?
EN

Stack Overflow用户
提问于 2018-06-07 18:08:51
回答 1查看 378关注 0票数 16

我在ConcurrentSkipListSet上使用descendingIterator方法。我刚刚查看了文档,并注意到以下注释:

‘升序视图及其迭代器比降序视图更快。’

请参阅https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentSkipListSet.html#descendingIterator--

不幸的是,它没有提供更多关于这方面的信息。有什么样的性能差异?它有意义吗?为什么会有性能上的差异?

EN

回答 1

Stack Overflow用户

发布于 2018-06-07 21:57:16

除了Stephen的回答之外,我还写了一个简单的基准测试:

代码语言:javascript
复制
@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方法:

代码语言:javascript
复制
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的代码示例,它在升序迭代器和降序迭代器中使用:

代码语言:javascript
复制
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元素的最终结果:

代码语言:javascript
复制
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元素:

代码语言:javascript
复制
Benchmark  Mode  Cnt   Score   Error  Units
ascItr     avgt    5   2,764 ± 1,160  ms/op
dscItr     avgt    5  11,110 ± 0,937  ms/op

可视化性能差异:

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50738555

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档