Сортированный поток, полученный из Infinite Stream, не может быть повторен

Question

import java.util.stream.*;
import java.util.*;

class TestInfiniteStream {
    public static void main(String args[]) {
        IntStream infiniteStream = new Random().ints();
        IntStream sortedStream = infiniteStream.sorted();

        sortedStream.forEach(i -> System.out.println(i));
    }
}

После компиляции и выполнения этого кода я получаю следующую ошибку.

Exception in thread "main" java.lang.IllegalArgumentException: Stream size exceeds max array size

Сбой сортировки потока в бесконечном потоке?

Answer 1

Ну, это интересный вопрос, к сожалению, ваше ключевое описание в комментариях. Прежде всего, в вашем случае нет действительно «бесконечного» потока, ответственный сплитератор RandomIntsSpliterator даже говорит, что:

... а также трактуя "бесконечность" как эквивалент Long.MAX_VALUE ...

А теперь самое интересное, что сплитератор сообщит эти характеристики:

public int characteristics() {
        return (Spliterator.SIZED | Spliterator.SUBSIZED |
                Spliterator.NONNULL | Spliterator.IMMUTABLE);
}

Ну, я не знаю причин почему , но сообщаю SIZED или SUBSIZED для бесконечного потока ... Может быть, это тоже не имеет значения (потому что вы обычно связываете эти с limit).

Хорошо, поскольку сообщается SIZED (размером Long.MAX_VALUE), для этого есть внутренняя раковина SizedIntSortingSink, которая имеет проверку:

if (size >= Nodes.MAX_ARRAY_SIZE)
      throw new IllegalArgumentException(Nodes.BAD_SIZE);

, который, очевидно, потерпит неудачу.

На контрасте IntStream.generate не сообщает SIZED - что имеет смысл для меня, поэтому весь вход должен быть буферизован sorted и позже обработан для работы терминала; очевидно, это не удастся с OutOfMemory.

Также интересно доказать, что distinct не будет действовать здесь как полный барьер, ожидая обработки всех значений. Вместо этого он может передать их в терминальную операцию, как только узнает, что этого раньше не было:

Random r = new Random();
IntStream.generate(() -> r.nextInt())
        .distinct()
        .forEach(System.out::println);

Это будет продолжаться довольно долго, прежде чем наконец умрет с OutOfMemory. или, как замечательно добавил Хольгер в комментариях, он тоже может зависнуть:

 IntStream.generate(() -> new Random()
          .nextInt(2))
          .distinct()
          .forEach(System.out::println);

Answer 2

Простой ответ на « Сбой сортировки потока в бесконечном потоке? » - « Да. » sorted() - это промежуточная операция с состоянием, которая была реализована путем буферизации все содержимое и сортировка перед передачей любых элементов в последующие операции.

Теоретически так быть не должно. Так как вы используете forEach, который был явно указан для обработки элементов в неопределенном порядке, шаг сортировки может быть пропущен в вашем new Random().ints().sorted().forEach(System.out::println); сценарии использования. Но даже если вы использовали forEachOrdered, есть теоретически достижимый правильный ответ. Поскольку ваш поток бесконечен и будет многократно содержать все значения int, правильный отсортированный вывод будет печатать -2147483648 (==Integer.MIN_VALUE) навсегда, поскольку это наименьшее значение, которое содержится в этом потоке бесконечное число раз.

Однако, чтобы дать этот правильный ответ, реализации потребуется конкретный код для обработки этого сценария, что не имеет большого практического значения. Вместо этого реализация обрабатывает этот случай, как и любая другая сортировка потокового сценария, которая завершится неудачей для бесконечных потоков.

В этом конкретном случае поток имеет оптимизацию, которая приводит к другому, необычному сообщению об исключении. Как указал Евгений , этот поток ведет себя как поток фиксированного размера из Long.MAX_VALUE (==2⁶³) элементов, а не как действительно бесконечный поток. Это справедливо, учитывая, что поток, генерируемый Random, будет повторяться после значений 2⁴⁸, поэтому весь поток был повторен 32768 раз, прежде чем он закончится, вместо того, чтобы работать вечно. Вы вряд ли станете свидетелями этого «внезапного» окончания после обработки 9223372036854775807 элементов в любом случае. Но следствием этой оптимизации является то, что поток будет быстро отказывать с сообщением «Размер потока превышает максимальный размер массива», а не с ошибкой «OutOfMemoryError» после некоторой обработки.

Если вы исключите информацию о размере, например, через

new Random().ints().filter(x -> true).sorted().forEach(System.out::println);

операция будет пытаться буферизироваться до сбоя с java.lang.OutOfMemoryError. То же самое происходит с

IntStream.generate(new Random()::nextInt).sorted().forEach(System.out::println);

, который в первую очередь не предоставляет информацию о размере для потока. В любом случае он никогда ничего не сортирует, поскольку буферизация происходит до начала сортировки.

Если вы хотите получить «отсортированные прогоны для некоторого ограничения элементов», как вы сказали в комментарии, вы должны применить ограничение перед сортировкой, например,

new Random().ints().limit(100).sorted().forEach(System.out::println);

хотя будет еще эффективнее использовать размерный поток, например

new Random().ints(100).sorted().forEach(System.out::println);

Answer 3

Нет, вы не можете сортировать бесконечный поток.

Ваш бесконечный поток new Random().ints() производит больше целых чисел, чем может быть сохранено в массиве (или любом массиве), который используется за кулисами для хранения целых чисел, которые будут отсортированы. Массив, конечно, не может содержать бесконечное число целых чисел; только емкость, близкая к Integer.MAX_VALUE числам .

Делая шаг назад, как кто-либо или что-либо сортирует бесконечное число целых чисел? Ничто не может и никто не может; это займет как минимум бесконечное количество времени.

Сбой сортировки потока в бесконечном потоке?

Вы как бы ответили на свой вопрос; IllegalArgumentException является конкретной причиной сбоя. Это произошло только потому, что вы создали программу, которая пыталась это сделать, и столкнулись с ограничением массива Java.

Метод sorted попытается прочитать весь поток перед сортировкой чего-либо. Он не будет выполнять промежуточную сортировку, пока не прочитает весь поток, поэтому сортировка не будет выполнена, частичная или полная.