Im использует метод descendingIterator для ConcurrentSkipListSet. Я только что проверил документацию и заметил следующий комментарий:
"Восходящие упорядоченные виды и их итераторы быстрее, чем нисходящие.
К сожалению, он не предоставляет больше информации об этом. Какая разница в производительности? это важно? и почему существует разница в производительности?
Если вы посмотрите на страницу Википедии " Пропустить списки", вы увидите, что они представляют собой сложную форму связанного списка со ссылками, идущими в направлении упорядочения записей списка. (На диаграмме это ясно видно...)
Когда вы перемещаете список пропусков в прямом направлении, вы просто следуете ссылкам. Каждый next() вызов является операцией O (1).
Когда вы перемещаете список пропусков в обратном направлении, каждый next() вызов должен найти ключ перед возвратом последнего ключа. Это операция O (logN).
(Тем не менее, перемещение списка пропусков в обратном направлении по-прежнему значительно быстрее, чем перемещение одиночно связанного списка назад. Это будет O (N) для каждого next() вызова next()...)
Если вы посмотрите под капот, вы увидите, что ConcurrentSkipListSet на самом деле является оберткой для ConcurrentSkipListMap. В этом классе объекты Node в представлении списка пропусков карты образуют односвязные цепи... в направлении восходящего ключа. Из предыдущего следует, что возрастающая итерация быстрее, чем нисходящая итерация.
Разница в производительности будет значительной, и она станет более значительной по мере увеличения установленного размера из-за разности O (1) по сравнению с O (logN).
В дополнение к ответу Стивена я написал простой контрольный показатель:
@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
Визуализация разницы в производительности:
