12

I have the following class:

public class Item {
    int id;
    String name;
    // few other fields, constructor, getters/setters
}

I have a list of Items. I want to iterate through the list and find the instance which has a particular id. I'm trying to do it through streams.

public void foobar() {
    List<Item> items = getItemList();
    List<Integer> ids = getIdsToLookup();
    int id, i = ids.size() - 1;
    while (i >= 0) {
        id = ids.get(i);
        Optional<Item> item = items
            .stream()
            .filter(a -> a.getId() == id)
            .findFirst();
        // do stuff
        i--;
    }
}

Is this the best way to iterate over the list and get the element I need? Also, I get an error on the filter line for id which says variables used in lambda expressions must be final or effectively final. Maybe I can define id inside the while loop, that should get rid of the exception. Thanks.

Improve this question
7
  • 1
    You're using the same variable i for the index in the list, and for the current item in the lambda. Choose a different name. That code is fine, but quite inefficient. If you have multiple ids and need to find the corresponding item for all, start by creating a HashMap<Integer, Item>, and then use the HashMap. Commented Mar 10, 2016 at 22:46
  • I'm using a different variable in my code, I was trying to simplify the code here. I'll change it. Commented Mar 10, 2016 at 22:49
  • 1
    Declare the variable id inside the loop, and it will be effectively final. By being outside, you reinitialize it at each iteration, and it's thus not final. Declaring variables in the smallest scope possible is a best practice in general. Commented Mar 10, 2016 at 22:52
  • Yeah, that's what I was thinking as well. Thanks for the suggestion. Commented Mar 10, 2016 at 22:55
  • 1
    Same for the loop BTW, use for (int i = 0; i < ids.size(); i++), or even better and simpler: for (Integer id : ids) Commented Mar 10, 2016 at 22:55

4 Answers 4

Reset to default
17

You can try use something like this:

ids.forEach(id -> 
    list.stream()
    .filter(p -> p.getId() == id)
    .findFirst()
    .ifPresent(p -> {
        // do stuff here
    });
);

Optional here shows that your filter() method can return an empty stream, so if you call findFirst() it can find one or zero elements.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

replacing findFirst() with findAny() would improve performance here. stackoverflow.com/questions/35359112/…
9

If you have lots of ids to search, it's recommended to use a solution which does it in a single pass rather than doing a linear search for each id:

Map<Integer,Optional<Item>> map=ids.stream()
    .collect(Collectors.toMap(id -> id, id -> Optional.empty()));
items.forEach(item ->
    map.computeIfPresent(item.getId(), (i,o)->o.isPresent()? o: Optional.of(item)));
for(ListIterator<Integer> it=ids.listIterator(ids.size()); it.hasPrevious();) {
    map.get(it.previous()).ifPresent(item -> {
        // do stuff
    });
}

The first statement simply create a map out of the ids list, mapping each search id to an empty Optional.

The second statement iterates over the items using forEach and for each item, it checks whether there’s a mapping from its id to an empty Optional and will replace it with an Optional encapsulating the item, if there is such a mapping, all in one operation, computeIfPresent.

The last for loop iterates backwards over the ids list, as you wished to process them in that order and perform the action if there’s a non-empty Optional. Since the map was initialized with all ids found in the list, get will never return null, it will return an empty Optional, if the id was not found in the items list.

That way, assuming that the Map’s lookup has O(1) time complexity, which is the case in typical implementations, the net time complexity changed from O(m×n) to O(m+n)…

Improve this answer

2 Comments

I like the idea of doing a single pass and getting all the required entries. But I need to process the entries in the order I received them in the ids list. I don't think the above code cares about ordering, right? Also, can you give some explanation of what you're trying to do in the above code? That will be helpful. Thanks.
@Gengis Khan: it does exactly what you want. The for loop is iterating backwards over the ids list as you wished.
2

If you want to stick with streams and iterate backwards, you could do it this way:

IntStream.iterate(ids.size() - 1, i -> i - 1)
    .limit(ids.size())
    .map(ids::get) // or .map(i -> ids.get(i))
    .forEach(id -> items.stream()
        .filter(item -> item.getId() == id)
        .findFirst().ifPresent(item -> {
            // do stuff
        }));

This code does the same as yours.

It iterates backwards, starting with a seed: ids.size() - 1. The initial stream of ints is limited in its size with limit(), so that there are no negative ints and the stream has the same size as the list of ids. Then, a map() operation converts the index to the actual id that is at the ith position at the ids list (this is done by means of invoking ids.get(i)). Finally, the item is searched in the items list the same way as in your code.

Improve this answer

3 Comments

The stream operation implies an O(n) complexity anyway…
@Holger I mean over ids list
@Holger Now I see what you mean, will edit to remove that note. Thanks!
1

You want to find at most one item for each given id and do something with the found item, right? A bit more performance improvement:

Set<Integer> idsToLookup = new HashSet<>(getIdsToLookup()); // replace list with Set

items.stream()
    .filter(e -> idsToLookup.remove(e.getId()))
    .forEach(
       /* doing something */
     );
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.