使用Stream从List中查找匹配昂贵条件的最后一个元素

Question

我有一个大约一百万个元素的有序列表，我正在寻找与特定条件匹配的最后一个元素，但是条件计算起来很重，所以如果我从头开始会更好。总是有大致的 log（n） 匹配元素，最小值为 1。

我可以手动操作：

List<Element> elements = ...;
Element element = null;
for (var it = elements.listIterator(elements.size()); it.hasPrevious(); ) {
  var candidate = it.previous();
  if (heavyConditionPredicate.test(candidate)) {
    element = candidate;
    break;
  }
}

有没有办法用< code>Streams来写这个，这样< code > heavyConditionPredicate 就不用对列表的每个元素进行测试了？如果heavyConditionPredicate计算起来不那么重，我会使用其他方法，但我没有那么幸运。

注意，< code>elements可以是任何类型的< code>List，我得到的那个不一定实现< code>RandomAccess，所以通过它们的索引访问列表可能也是代价很高的。

Answer 1

Stream的当前实现（从Java11开始）的缺点是它不允许以相反的顺序处理项目。您必须为其提供具有指定顺序的源：

List<Element> elements = new ArrayList<>();
List<Element> reversedElements = new ArrayList<>(elements);
Collections.reverse(reversedElements);

Element element =  reversedElements.stream().filter(heavyConditionPredicate).findFirst().orElse(null);

另一种方法是利用Deque接口的优势，该接口提供Deque::descendingIterator：

Deque<Element> elements = new ArrayDeque<>();
Iterator<Element> it = elements.descendingIterator()

使用Deque::推送，您可以创建一个自定义StreamUtils方法来反转传递的Stream，而无需使用外部库：

class StreamUtils {
    static <T> Stream<T> reverse(Stream<T> stream) {
        Deque<T> deque = new ArrayDeque<>();
        stream.forEach(deque::push);
        return deque.stream();
    }
}

...

Element element = StreamUtils.reverse(elements.stream())
    .filter(heavyConditionPredicate)
    .findFirst().orElse(null);

Answer 2

Guava的< code>Lists::reverse在这里肯定有帮助，因为它是一个视图，它不修改我的列表，也不通过索引访问元素:

Lists.reverse(elements).stream()
  .filter(heavyConditionPredicate)
  .findFirst();