如何在Java 8中从列表中获取倒序的有序流

Question

有没有一种合理的方式可以从列表（特别是数组列表，但这并不重要）中获取有序流，该流以与原始列表中相反的顺序流元素？

我正在寻找一种解决方案，它不涉及在任何东西中缓冲数据（收集器、另一个列表、数组等，因为它们会复制容器，这是浪费的），也不使用Collections.reverse（因为它修改了列表）。

到目前为止，我看到这里最干净的方法是实现我的自己版本的Spliterator，它是ORDERED并且倒序遍历列表，或者实现一个倒序迭代器，并在其上使用Spliterators.spliteratorUnknownSize（iterator，ORDERED）。

请注意，此问题与Java 8 stream reverse order不同：那个问题问如何翻转流（在一般情况下是不可能的），并且答案提供了某种方式来翻转源（我不想这样做），然后流式传输该翻转源。 翻转源的成本为O（N），如果可能的话，我想尽可能避免它。

- Pawel Veselov

---

本文涵盖了几种可能性：http://www.leveluplunch.com/java/tutorials/028-reverse-order-stream-elements-java8/ - izilotti

Answer 1

如果您的List是一个随机访问列表，那么您可以简单地使用

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

创建一个具有特性 ORDERED | SIZED | SUBSIZED 并提供完整分割支持的 Stream。

对于像 LinkedList 这样没有随机访问的列表，它将是一场性能灾难，但是，谁会使用 LinkedList 呢？

您还可以首先通过 list instanceofRandomAccess 进行检查...

- Holger

---

嘿，我应该先想到这个。+1。我想我太着迷于编写反向分隔器的想法了。 - Stuart Marks

或者 IntStream.rangeClosed(1, list.size()).mapToObj(i -> list.get(list.size() - i))。 - shmosel

Answer 2

注意：如果您有一个允许通过索引进行随机访问检索（get(i)）的ArrayList或其他列表，则Holger's approach更可取。下面的方法仅在您拥有一种允许反向遍历但不允许索引访问的数据结构时才是必要的。

---

很不幸，似乎没有真正简单的方法（即一行代码）来实现这一点。但是，使用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的，但这在{{link1：不可分割的spliterator}}上大多是无意义的。）

目前情况下，这可以提供有限的并行度，因为AbstractSpliterator会多次调用tryAdvance并批量处理工作以移交给分叉-加入任务。但这并不像能够切分那样有效。

如果并行效率是一个重要问题，那么可以编写一个实际上可以拆分的Spliterator，其中拆分是以相反顺序遍历的。

- Stuart Marks

---

ι²ΘδΙàοΦ¨δΫΩγî® AbstractSpliterator φ·î IteratorSpliterator φ¦¥εΞΫοΦü - Pawel Veselov

我不认为 SIZED 是无意义的。但是 SUBSIZED 就没有意义了。 - Holger

@PawelVeselov 我认为 AbstractSpliterator 比编写自己的迭代器要容易一些。但是如果你已经有了一个迭代器，那么使用 Spliterators.spliteratorUnknownSize(iterator, ...) -- 它在底层使用 IteratorSpliterator -- 肯定更容易编码。 - Stuart Marks

@Holger 是的，SIZED 可能会使流进行更好的缓冲，但我不确定。在 JDK 9 中，它将允许 count() 进行短路。 - Stuart Marks

@StuartMarks 我更在意的是任何实现执行上的优势。我所看到的AbstractIterator唯一的缺点是它的trySplit()方法会多产生一个对象(HoldingConsumer)。(顺便问候一下，好久不见了 :) ) - Pawel Veselov

@PawelVeselov（我想你是指AbstractSpliterator？）这里有一些权衡。 IteratorSpliterator不需要HoldingConsumer，但它需要每个元素进行额外的方法调用（hasNext+next）。但这可能会被Consumer.accept的调用所抵消...嗯。好吧，我认为唯一真正的找出方法就是去测量。 （而且，是的，已经过了一段时间！） :-) - Stuart Marks

Answer 3

Google的Guava库提供了一个列表的反向视图(Lists#reverse(List))。Apache Commons Collection库中也有一个ReverseListIterator。

- teppic

Answer 4

我最近找到了这个解决方案。

public <T> Stream<T> toReverseStream(List<T> list) {
    ListIterator<T> listIterator = list.listIterator(list.size());
    return Stream.generate(listIterator::previous)
            .limit(list.size());
}

- Karl Karlson

---

这不是一个好主意。Stream.generate(…) 创建的是一个无序流。此外，流的阶段不应该依赖于后续阶段的效果。换句话说，并不能保证供应者的评估次数仅仅是由限制指定的。在顺序上下文中可能会做到期望的事情，但在实际的并行执行中可能会失败。但在正式层面上，无论哪种情况都是错误的。 - undefined

Answer 5

从即将发布的Java 21开始，reversed()方法可以用来返回列表的反转视图，然后可以对其进行流式处理。

Stream<Object> reversedStream = list.reversed().stream();

根据要求，这个操作不会缓冲或复制数据，因为它只是原始列表的反向视图。

- M. Justin

Answer 6

我倾向于采用@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();
        }
    };
}

- Matt McHenry