guava - Iterables avoid iterating multiple times

Question

I have a list of objects that contains two string properties.

public class A {
    public String a;
    public String b;
}

I want to retrieve two Sets one containing property a and one b.

The naive approach is something long these lines:

List<A> list = ....
Set<String> listofa = new HashSet<>();
Set<String> listofb = new HashSet<>();
for (A item : list) {
    if (item.a != null) 
        listofa.add(item.a);
    if (item.b != null) 
        listofb.add(item.b);

}

Trying to do in a functional way in guava I ended up with this approach:

Function<String,A> getAFromList = new Function<>() {
    @Nullable
    @Override
    public String apply(@Nullable A input) {
        return input.a;
    }
};

Function<String,A> getBFromList = Function<>() {
    @Nullable
    @Override
    public String apply(@Nullable A input) {
        return input.b;
    }
};

FluentIterable<A> iterables = FluentIterable.from(list);

Set<String> listofAs = ImmutableSet.copyOf(iterables.transform(getAFromList).filter(Predicates.notNull()));

Set<String> listofBs = ImmutableSet.copyOf(iterables.transform(getBFromList).filter(Predicates.notNull()));

However this way I would iterate twice over the list.

Is there any way how to avoid iterating twice or multiple times ?

In general how does one solve these uses cases in a functional way in general (not only in guava/java) ?

score 1 · Answer 1 · edited May 23 '17 at 11:44

Firstly you're after an optimisation - but if performance is key, use regular java methods over guava (i.e. your first method). See here.

I think because you want two results, at some point you will need to iterate twice (unless you pass in one of the sets to be populated but that that is definitely not a fp approach as it would not be a pure function).

However if iteration was expensive enough to need an optimisation you would iterate that once to an intermediate structure:

a_b_pairs = transformToJustAB(input) //single expensive iteration
list_of_a = transformA(a_b_pairs) //multiple cheaper iterations
list_of_b = transformB(a_b_pairs)

score 1 · Answer 2 · answered Jan 26 '15 at 17:26

1

So the simple answer is that you have to iterate twice. Think about it. If you have N elements in your List you will need to do N inserts into the first Set and N inserts into the second Set. Functional or otherwise, you will have to iterate N twice whether it be on conversion (extraction) or insert.

If you were going for two Lists it would be different because you could create views and only iterate as needed.

answered Jan 26 '15 at 17:26

John B

32,493
6
77
98

Hmm I am not sure I can follow. How would this be different when I use `Lists` ? I still have to iterate twice over the initial list. Even if I only have lazily consumed view, when I access the items in those two lists, it will have to iterate over the list twice the same way as with Sets. Or am I missing something ? – Ümit Jan 26 '15 at 17:36
No, you are correct. Initialization via a view would be O(1) but once you iterate to access the elements you are at O(N). This strategy would only work well if you don't always iterate one or both collections. – John B Jan 26 '15 at 17:52

score 1 · Answer 3 · edited May 23 '17 at 11:58

1

What you're trying to achieve is partitioning or splitting of the collection using predicates.

With Guava, you can use Multimap.index. See related question and answer here.

edited May 23 '17 at 11:58

Community

1
1

answered Jan 26 '15 at 21:19

Sauli Tähkäpää

2,034
1
10
9

score 1 · Answer 4 · answered Jan 30 '15 at 11:16

This can be solved in one iteration with Multimaps.index:

    Function<A, String> filterAB = new Function<A, String>() {
        @Override
        public String apply(A input) {

            if (input.a != null) {
                return "a";
            }
            if (input.b != null) {
                return "b";
            }
            return "empty";
        }
    };

    ImmutableListMultimap<String, A> partitionedMap = Multimaps.index(list, filterAB);

The output will be a Guava Multimap with three separate entries for:

an immutable list with all "a-not-null" objects under key "a".
an immutable list with all "b-not-null" objects under key "b".
and possibly an immutable list with objects where both a and b is null under key "empty".

guava - Iterables avoid iterating multiple times

4 Answers4