英文:
Find the last element matching an expensive condition from a List, using Stream
问题
List<Element> elements = ...;
Element element = IntStream.range(0, elements.size())
.mapToObj(i -> elements.get(elements.size() - 1 - i))
.filter(heavyConditionPredicate)
.findFirst()
.orElse(null);
英文:
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.
答案1
得分: 4
Guava的Lists::reverse在这里绝对有帮助，因为它是一个视图，不会修改我的列表，也不会通过索引访问元素：
Lists.reverse(elements).stream()
.filter(heavyConditionPredicate)
.findFirst();
英文:
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();
答案2
得分: 1
目前的`Stream`实现（截至Java 11）的缺点是它不允许以相反的顺序处理项目。您必须为其提供具有指定顺序的源：
List<Element> elements = new ArrayList<>();
List<Element> reversedElements = new ArrayList<>(elements);
Collections.reverse(reversedElements);
Element element = reversedElements.stream().filter(heavyConditionPredicate).findFirst().orElse(null);
另一种方法是利用[`Deque`][1]接口的优势，它提供了[`Deque::descendingIterator`][2]：
Deque<Element> elements = new ArrayDeque<>();
Iterator<Element> it = elements.descendingIterator()
使用[`Deque::push`][3]，您可以创建一个自定义的`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);
[1]: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html
[2]: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html#descendingIterator()
[3]: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Deque.html#push(E)
英文:
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);
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论