Stream with sorted() before findFirst() is no longer lazy

Question

I have a list of elements, I need to find the first element that satisfy the condition then exit using Java 8 streams.

I think the following code unfortunately evaluate all available element which doesn't what i need, I need to evaluate items one by one and stop (break) when find the first match:

I am here sorting the elements, then map the element to its url attribute then try to filter if the url is not null or empty then find first match!

Arrays.stream(dataArray)
.sorted(Comparator.comparing(d -> d.getPriority()))
.peek(o -> System.out.println("SORT: " + o))
.map(d -> d.getOriginalURL(shortUrl))
.peek(o -> System.out.println("MAP: " + o))
.filter(u -> u != null && !u.isEmpty())
.peek(o -> System.out.println("FILTER: " + o))
.findFirst().orElse("");

But the output shows that, all items are evaulated even if the first one matches the if condition (filter) operation.

Data[] data = new Data[] { new ParseData(), new InMemoryData() };
System.out.println(">>> " + getOriginalURL(data, ""));

OUTPUT:

SORT: mhewedy.usingspark.data.InMemoryData@7adf9f5f
MAP: InMemory URL
FILTER: InMemory URL
SORT: mhewedy.usingspark.data.ParseData@85ede7b
MAP: Parse.com URL         <<< THIS SHOULD NOT HAPPEN
FILTER: Parse.com URL      <<< AND THIS TOO
>>> InMemory URL

As output shows, the stream doesn't stop when the filter matches with the first element, instead it continue evaluating the second element too!

I want to do like this:

Arrays.sort(dataArray, Comparator.comparing(d -> d.getPriority())); // sort

for (Data data : dataArray) {
    String url = data.getOriginalURL(shortUrl);           // map
    if (url != null && !url.isEmpty()) {                  // filter
        System.out.println("url :" + url);            
        return url;                                   // find first
    }
}

Answer 1

The sorted operation forces traversal of all the items in the stream.

Stateful operations, such as distinct and sorted, may incorporate state from previously seen elements when processing new elements.

Stateful operations may need to process the entire input before producing a result. For example, one cannot produce any results from sorting a stream until one has seen all elements of the stream.

(Source)

I'm not sure, though, why the operations following the sorted are also executed for all the elements in the stream.

If you perform the sort separately, and then use the stream for the rest of the processing, the processing will stop when the first match is found, as expected.

Arrays.sort(dataArray, Comparator.comparing(d -> d.getPriority())); // sort

Arrays.stream(dataArray)
.peek(o -> System.out.println("SORT: " + o))
.map(d -> d.getOriginalURL(shortUrl))
.peek(o -> System.out.println("MAP: " + o))
.filter(u -> u != null && !u.isEmpty())
.peek(o -> System.out.println("FILTER: " + o))
.findFirst().orElse("");

Answer 2

Here's a smaller example that illustrates the issue:

Stream.of("a", "ab", "abc", "abcd")
    // .sorted() // uncomment and what follows becomes eager
    .filter(s -> s.contains("b"))
    .peek(s -> System.out.println("PEEK: " + s))
    .findFirst()
    .orElse("X");

As expected the output is:

PEEK: ab

If the sorted line is uncommented, the output is:

PEEK: ab
PEEK: abc
PEEK: abcd

(The final result of the entire pipeline is "ab" in both cases, as expected.)

It's true that sorted must consume all of its input before producing its first output element. In that sense it's eager. However, it does seem strange that it affects how elements are sent downstream.

Without sorting, the findFirst operation "pulls" elements from upstream until it finds one, and then it stops. With sorting, the sorted() operation eagerly gathers all the elements, sorts them, and since it has them all right there, it "pushes" them down the stream. Of course, findFirst ignores all but the first element. But this means that intervening operations (such as the filter) may do unnecessary work.

The final result is correct, but the behavior is unexpected. This might be considered a bug. I'll investigate and file a bug if appropriate.

Answer 3

What you want to use is stream.collect(minBy(...)). It has linear performance.

The minBy static method is found on the Collectors class.