Насколько специализированы потоковые реализации, возвращаемые стандартными коллекциями?

Stream - это интерфейс, поэтому всякий раз, когда вы получаете объект Stream, скрывается множество скрытых деталей реализации.

Например, возьмите следующий код:

List<String> list = new ArrayList<>();
...
int size = list.stream()
               .count();

Работает ли он в постоянном или линейном времени? Или это:

Set<String> set = new TreeSet<>();
...
set.stream()
   .sorted()
   .forEach(System.out::println);

Будет ли это O (n) или O (n log n)?

В целом, как специализированные реализации потоков, возвращаемые стандартными коллекциями?

Ответы

Ответ 1

Работает ли он в постоянном или линейном времени?

Текущая реализация выполняется в линейном времени:

public final long count() {
    return mapToLong(e -> 1L).sum();
}

Но это может быть улучшено (там RFE для этого где-то), чтобы работать в постоянное время в некоторых ситуациях.

Как? Поток описывается источником потока, нулевыми или более промежуточными операциями и терминальной операцией (здесь count() - операция терминала). Реализация потока поддерживает набор характеристик об источнике и знает, как характеристики изменяются операциями. Например, поток, поддерживаемый коллекцией, имеет характеристику SIZED, тогда как поток, поддерживаемый Iterator, не имеет размера. Точно так же операция map() сохраняется в размере, но операция filter() уничтожает любые априорные знания о размерах. Реализация потока знает составные характеристики конвейера, прежде чем он запустит операцию терминала, поэтому он знает, зависит ли исходный размер и все ли размеры сохраняются по размеру, и в таких случаях может просто задать источник для размера и обойти все фактическое вычисление потока. (Но реализация на Java 8 не выполняется).

Обратите внимание, что потоки не должны быть специализированными для поддержки этого; классы Collection создают поток с Spliterator, который знает его характеристики, поэтому специализированная реализация для Collections не нужна, просто обновляя общую реализацию, чтобы использовать этот конкретный бит информации.

Ответ 2

Метод sorted() не изменяет размер, поэтому теоретически возможно, что будущая реализация может сделать цепочку stream().sorted().count() в O(1) времени.

Взгляните на реализацию [speedment] с открытым исходным кодом интерфейса Stream в https://github.com/speedment/speedment. Эти потоки могут анализировать собственный конвейер и оптимизировать один или несколько шагов в потоке.