Find the last element matching an expensive condition from a List, using Stream

user_180719 0
Viewed 2728

I have an ordered List of roughly one million elements of which I'm looking for the last element that matches a specific condition, but the condition is heavy to compute so it's better if I start from the end instead. There are always roughly log(n) matching elements, with a minimum of 1.

I can do it manually:

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;
  }
}

Is there any way to write this using Streams, so that the heavyConditionPredicate is not tested against each element of the list? If the heavyConditionPredicate would not have been so heavy to compute, I'd have used alternative means, but I'm not that lucky.

Note that elements can be any type of List, and the one I get doesn't necessarily implements RandomAccess, so accessing the list by their index might be costly as well.

java-stream list java
2 Answers

Guava's Lists::reverse definitely helps here, as it's a view and it doesn't modify my list and it doesn't access elements by their index:

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

The disadvantage of the current implementation (as of Java 11) of Stream is that it doesn't allow to process items in the reverse order. You have to provide it the source with the specified order:

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

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

Another way is to use the advantage of the Deque interface that offers Deque::descendingIterator:

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

With Deque::push you can create a custom StreamUtils method reversing the passed Stream with no need of using an external library:

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);
user_37649650
Related