Найти последний элемент, соответствующий дорогостоящему условию из списка, используя Stream

Question

У меня есть заказанный List примерно из миллиона элементов, из которых я ищу последний элемент, который соответствует указанному условию c, но условие тяжело вычислить, поэтому лучше, если я начну с конца вместо. Всегда есть примерно 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;
  }
}

Есть ли способ написать это, используя Stream s, так что heavyConditionPredicate не проверяется по каждому элементу списка? Если бы HeavyConditionPredicate не был бы таким тяжелым для вычислений, я бы использовал альтернативные средства , но мне не везет.

Обратите внимание, что elements может быть любым типом List, а тот, который я получаю, не обязательно реализует RandomAccess, поэтому доступ к списку по их индексу также может быть дорогостоящим.

Answer 1

Недостатком текущей реализации (по состоянию на Java 11) Stream является то, что она не позволяет обрабатывать элементы в обратном порядке. Вы должны предоставить ему источник в указанном порядке:

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* 1010. *:

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

С помощью Deque::push вы можете создать пользовательский метод 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's Lists::reverse определенно помогает здесь, так как это представление, оно не изменяет мой список и не обращается к элементам по их индексу:

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