Как получить упорядоченный поток из списка в обратном порядке в Java 8

Есть ли разумный способ получить упорядоченный поток из списка (список массивов конкретно, но это не имеет значения), который передает элементы в обратном порядке, как они находятся в исходном списке?

Я ищу решение, которое не включает в себя буферизацию данных во всем (сборщик, другой список, массив и т.д., поскольку они копируют контейнер, который расточительно) или использует Collections.reverse (поскольку он изменяет список).

До сих пор самые чистые способы, которые я вижу здесь, - реализовать мою собственную версию Spliterator, которая ORDERED и продвигается через список в обратном порядке, или реализовать Iterator, который выполняет итерацию в обратном порядке, и использовать Spliterators.spliteratorUnknownSize(iterator,ORDERED) на нем.

Обратите внимание, что этот вопрос отличается от обратного порядка потока Java 8: этот другой вопрос задает вопрос о том, как изменить поток (что невозможно в общем случае) и ответы предложите каким-то образом изменить исходный код (чего я не хочу делать), а затем поток, который изменил исходный код. Стоимость реверсирования источника - O (N), и я хочу вообще избежать его, если это возможно.

Ответы

Ответ 1

Если ваш List является списком произвольного доступа, вы можете просто использовать

int num=list.size()-1;
IntStream.rangeClosed(0, num).mapToObj(i->list.get(num-i))

чтобы создать Stream, который имеет характеристики ORDERED | SIZED | SUBSIZED и предлагает полную поддержку разбиения.

Для списка неслучайного доступа, такого как LinkedList, это будет катастрофой производительности, однако, кто использует LinkedList в любом случае?

Вы также можете сначала проверить list instanceof RandomAccess...

Ответ 2

ПРИМЕЧАНИЕ. Если у вас есть ArrayList или другой список, который позволяет получить произвольный доступ по индексу (get(i)), тогда подход Холгера является предпочтительным. Подход ниже необходим только в том случае, если у вас есть структура данных, которая позволяет обратный обход, но не индексированный доступ.

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

static <T> Stream<T> reversedStream(List<? extends T> input) {
    ListIterator<? extends T> li = input.listIterator(input.size());
    return StreamSupport.stream(
        new Spliterators.AbstractSpliterator<T>(input.size(), Spliterator.ORDERED) {
            @Override public boolean tryAdvance(Consumer<? super T> action) {
                if (li.hasPrevious()) {
                    action.accept(li.previous());
                    return true;
                } else {
                    return false;
                }
            }
        },
        false);
}

(Я полагаю, что Spliterator может быть SIZED, но это в основном бессмысленно, потому что это unsplittable spliterator.)

Как бы то ни было, это может обеспечить ограниченную степень parallelism, так как AbstractSpliterator будет многократно называть tryAdvance и выполнять пакетную работу, чтобы отдать на выполнение задач fork-join. Но это не так эффективно, как возможность разделить.

Если параллельная эффективность является большой проблемой, можно написать разделитель, который может фактически разделиться, где разрывы пересекаются в обратном порядке.

Ответ 3

Библиотека Google Guava предоставляет обратное представление списка (Lists#reverse(List)). В библиотеке Apache Commons Collection есть ReverseListIterator.

Ответ 4

Мне нравится @teppic ответ об использовании сторонней библиотеки для этого. Тем не менее, это интересное упражнение, чтобы попытаться придумать решение, используя только Java 8 API. Делегирование на ListIterator - самая чистая вещь, которую я мог бы придумать, но она не намного чище, чем реализация вашего собственного Iterator с нуля.

public static void main(String[] args){
    List<String> l = Arrays.asList("first", "second", "third");

    StreamSupport.stream(Spliterators.spliterator(revit(l), l.size(), 0), false)
                 .forEachOrdered(System.out::println);
}

private static final <T> Iterator<T> revit(List<T> l){
    ListIterator<T> li = l.listIterator(l.size());

    return new Iterator<T>(){
        @Override
        public boolean hasNext(){
            return li.hasPrevious();
        }

        @Override
        public T next(){
            return li.previous();
        }
    };
}