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

Question

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.

Since you mentioned ordered list I would assume its sorted, you can use `Collections.binarySearch(list, 10); // assuming you are searching for 10.` If it is not sorted, you can try sorting it and then perform binarySearch. — Rupesh, Apr 07 '20 at 12:28
@Rupesh No, [it's not sorted: it's ordered](https://stackoverflow.com/questions/1084146/what-is-the-difference-between-an-ordered-and-a-sorted-collection). Also, the ordering and the search criteria are not linked. — Olivier Grégoire, Apr 07 '20 at 12:30
@Naman Would you clarify your usage of `IntStream` further? Why would it be appropriate? — Olivier Grégoire, Apr 07 '20 at 12:32
Is the list implementation known / fixed / changeable ? Is it `RandomAccess`ible ? — GPI, Apr 07 '20 at 12:34
@GPI My edit in the question and your comment happened at the same time. Please reload the question as your comment is answered. — Olivier Grégoire, Apr 07 '20 at 12:37
@OlivierGrégoire `IntStream.iterate(elements.size(), i -> i > 0, i -> i - 1) .filter(i -> heavyConditionPredicate.test(elements.get(i))) .findFirst();` is what I meant, but not sure about the thread safety when that's executed in parallel. This uses the API `IntStream iterate(int seed, IntPredicate hasNext, IntUnaryOperator next)` — Naman, Apr 07 '20 at 12:39
@Naman I guessed that was the idea behind your last comment so I edited the question accordingly. The list is used only for its ordered property, therefore `List::get` might be costly. — Olivier Grégoire, Apr 07 '20 at 12:46
@OlivierGrégoire sure, not a straightforward way in Stream that I know of, might just be a custom `Spliterator` defined. Let's wait for better people to answer. — Naman, Apr 07 '20 at 13:07
[How to get ordered stream from a list in reverse order in Java 8](https://stackoverflow.com/q/29403614/2711488) — Holger, Apr 08 '20 at 11:15
To whoever added the tag `java-8`, the code in the question is at least `java-10`... Please don't add tag unless they're actually correct. — Olivier Grégoire, Apr 09 '20 at 12:46

score 4 · Answer 1 · answered Apr 07 '20 at 15:58

4

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();

answered Apr 07 '20 at 15:58

Olivier Grégoire

33,839
23
96
137

I wonder what the implementation of `Lists.reverse(elements)` is? I would definitely take a look at it as well. – Naman Apr 08 '20 at 04:29
1

@Naman I suppose, a simple wrapper with adapted `get` and `iterator`/`listIterator` methods. More wouldn’t be necessary. In the best case, it also has an adapted `spliterator` method, which would make `stream()` efficient. See also [How to get ordered stream from a list in reverse order in Java 8](https://stackoverflow.com/q/29403614/2711488)… – Holger Apr 08 '20 at 11:17
1

[This answer](https://stackoverflow.com/a/42239024/2711488) is also interesting… – Holger Apr 08 '20 at 12:22
@Naman Guava is open source, you're very welcome to [check the implementation online](https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Lists.java#L793). – Olivier Grégoire Apr 09 '20 at 12:09

Nikolas Charalambidis · Answer 2 · 2020-04-07T17:12:20.087

2

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

edited Apr 07 '20 at 17:12

answered Apr 07 '20 at 17:05

Nikolas Charalambidis

40,893
16
117
183

Correct me if I am wrong but in both your solution you end up iterating the complete list once at least, which would be costly as mentioned in the question by OP. – Naman Apr 08 '20 at 04:27
Nope, it doesn't iterate through all the elements but only until the first element is qualified. `Stream::findFirst` is a short-circuiting operation. See: https://onlinegdb.com/By8AYHsPI – Nikolas Charalambidis Apr 08 '20 at 12:57
`Collections.reverse` or even your `StreamUtils.reverse` iterates on the list. So yes, there is a full iteration at least once. But iterating isn't costly: only `get(int)` can be costly. Iterating doesn't especially result in `get(int)` being called. – Olivier Grégoire Apr 09 '20 at 12:54
Yes, that's what I meant, but I wasn't clean. The iteration with the costly predicate doesn't take necessarily all the elements, but the reversing the collection itself does (although it is cheap). – Nikolas Charalambidis Apr 09 '20 at 13:07

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

2 Answers2