Find first element by predicate

Question

I've just started playing with Java 8 lambdas and I'm trying to implement some of the things that I'm used to in functional languages.

For example, most functional languages have some kind of find function that operates on sequences, or lists that returns the first element, for which the predicate is true. The only way I can see to achieve this in Java 8 is:

lst.stream()
    .filter(x -> x > 5)
    .findFirst()

However this seems inefficient to me, as the filter will scan the whole list, at least to my understanding (which could be wrong). Is there a better way?

Answer 1

@BeJay is right, it's a bad practice to use null values in that context. NPE should only appear in the context of a code error like any forgotten or failed instantiation, null cannot be use to hold a meaningful value ( data not found ). It's a bit like the benefits of banning the use of magic numbers.

public static void main(String[] args)
{
    List<Integer> List1 = List.of( 3, 14, 15, 9, 26);
    List<Integer> List2 = List.of( 5, 16, 3, 2, 1);
    // intend to be use as a stack of "to scan" Lists
    ArrayList<List<Integer>> parentList = new ArrayList<>( List.of(List1,List2));
    Optional<Integer> multipleOfFour = Optional.empty();
    //looping while parentList still contains sub-list(s) and no multiple of 4 was found
    while ( ! parentList.isEmpty() && multipleOfFour.isEmpty())
    {
        //popping out first element of parentList
        List<Integer> currentList = parentList.remove(0);
        multipleOfFour = currentList.stream().filter(num->num%4 == 0).findFirst();
    }
    if ( ! multipleOfFour.isPresent())
    {
        //cheating in case no multiple of 4 was found in any of the 2 lists
        multipleOfFour = Optional.of(Integer.valueOf(4));
    }
    // never use get() unless absolutely sure isPresent()
    // would return true or an exception could be thrown
    System.out.println("first multiple of 4 found: " + multipleOfFour.get());
}

Now if I didn't instantiate multipleOfFour with Optional.empty() when declared, a NPE will occur when attempting to call isEmpty() in the while loop condition, and I'll know for sure the error comes from the code itself.

On the other hand if multipleOfFour.isPresent() doesn't return true when I expect, I'll know for sure the error comes either from the data provided or from the stream lambda that doesn't operate properly.

Easier to debug when you know where to look...

That Opened my eyes, I rewrote the method of recursive search I was working on, using Optional.empty() instead of null. Thank you @BeJay

Answer 2

A generic utility function with looping seems a lot cleaner to me:

static public <T> T find(List<T> elements, Predicate<T> p) {
    for (T item : elements) if (p.test(item)) return item;
    return null;
}

static public <T> T find(T[] elements, Predicate<T> p) {
    for (T item : elements) if (p.test(item)) return item;
    return null;
}

In use:

List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5);
Integer[] intArr = new Integer[]{1, 2, 3, 4, 5};

System.out.println(find(intList, i -> i % 2 == 0)); // 2
System.out.println(find(intArr, i -> i % 2 != 0)); // 1
System.out.println(find(intList, i -> i > 5)); // null

Answer 3

Already answered by @AjaxLeung, but in comments and hard to find.
For check only

lst.stream()
    .filter(x -> x > 5)
    .findFirst()
    .isPresent()

is simplified to

lst.stream()
    .anyMatch(x -> x > 5)

Answer 4

return dataSource.getParkingLots()
                 .stream()
                 .filter(parkingLot -> Objects.equals(parkingLot.getId(), id))
                 .findFirst()
                 .orElse(null);

I had to filter out only one object from a list of objects. So i used this, hope it helps.

Answer 5

Improved One-Liner answer: If you are looking for a boolean return value, we can do it better by adding isPresent:

return dataSource.getParkingLots().stream().filter(parkingLot -> Objects.equals(parkingLot.getId(), id)).findFirst().isPresent();

Answer 6

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.Optional;

// Stream is ~30 times slower for same operation...
public class StreamPerfTest {

    int iterations = 100;
    List<Integer> list = Arrays.asList(1, 10, 3, 7, 5);


    // 55 ms
    @Test
    public void stream() {

        for (int i = 0; i < iterations; i++) {
            Optional<Integer> result = list.stream()
                    .filter(x -> x > 5)
                    .findFirst();

            System.out.println(result.orElse(null));
        }
    }

    // 2 ms
    @Test
    public void loop() {

        for (int i = 0; i < iterations; i++) {
            Integer result = null;
            for (Integer walk : list) {
                if (walk > 5) {
                    result = walk;
                    break;
                }
            }
            System.out.println(result);
        }
    }
}

Answer 7

In addition to Alexis C's answer, If you are working with an array list, in which you are not sure whether the element you are searching for exists, use this.

Integer a = list.stream()
                .peek(num -> System.out.println("will filter " + num))
                .filter(x -> x > 5)
                .findFirst()
                .orElse(null);

Then you could simply check whether a is null.

Answer 8

No, filter does not scan the whole stream. It's an intermediate operation, which returns a lazy stream (actually all intermediate operations return a lazy stream). To convince you, you can simply do the following test:

List<Integer> list = Arrays.asList(1, 10, 3, 7, 5);
int a = list.stream()
            .peek(num -> System.out.println("will filter " + num))
            .filter(x -> x > 5)
            .findFirst()
            .get();
System.out.println(a);

Which outputs:

will filter 1
will filter 10
10

You see that only the two first elements of the stream are actually processed.

So you can go with your approach which is perfectly fine.

Answer 9

However this seems inefficient to me, as the filter will scan the whole list

No it won't - it will "break" as soon as the first element satisfying the predicate is found. You can read more about laziness in the stream package javadoc, in particular (emphasis mine):

Many stream operations, such as filtering, mapping, or duplicate removal, can be implemented lazily, exposing opportunities for optimization. For example, "find the first String with three consecutive vowels" need not examine all the input strings. Stream operations are divided into intermediate (Stream-producing) operations and terminal (value- or side-effect-producing) operations. Intermediate operations are always lazy.