Collect stream with grouping, counting and filtering operations

14
votes

I'm trying to collect stream throwing away rarely used items like in this example:

import java.util.*;
import java.util.function.Function;
import static java.util.stream.Collectors.*;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.containsInAnyOrder;
import org.junit.Test;

@Test
public void shouldFilterCommonlyUsedWords() {
    // given
    List<String> allWords = Arrays.asList(
       "call", "feel", "call", "very", "call", "very", "feel", "very", "any");

    // when
    Set<String> commonlyUsed = allWords.stream()
            .collect(groupingBy(Function.identity(), counting()))
            .entrySet().stream().filter(e -> e.getValue() > 2)
            .map(Map.Entry::getKey).collect(toSet());

    // then
    assertThat(commonlyUsed, containsInAnyOrder("call", "very"));
}

I have a feeling that it is possible to do it much simpler - am I right?

3
javajava-8java-stream
No, that looks like about the simplest way to do it. – Louis Wasserman
You can replace new ArrayList<>(Arrays.asList(…)) by a simple Arrays.asList(…). There is only one way to avoid a map which is calculating the frequency again for each item but that’s O(n²) CPU complexity, so I guess you better live with the intermediate map… – Holger
What this question attempts to do is equivalent to the SQL statement SELECT word FROM allWords GROUP BY word HAVING count(*) > 2. The groupingBy Collector does the job of GROUP BY, but there is no HAVING clause equivalent. It would be good for Java to add that functionality, e.g. something like groupingBy(Function<? super T,? extends K> classifier, Collector<? super T,A,D> downstream, Predicate<? super D> having). – rgettman
@rgettman: I don’t see the advantage of such a method. It’s only hiding the fact that it has to collect the entire map first, before filtering just like in my answer… – Holger
@Holger Then why have a HAVING clause in SQL? It's just hiding the fact that the group by and aggregate operations happen before the aggregate values are filtered. Once could write SELECT word FROM (SELECT word, count(*) c FROM allWords GROUP BY word) WHERE c > 2;. Having HAVING allows more concise code. One can certainly use your solution; it will work. I just pointed out that it would be good for Java to have the HAVING option that would simplify the code. – rgettman

3 Answers

10
votes

There is no way around creating a Map, unless you want accept a very high CPU complexity.

However, you can remove the second collect operation:

Map<String,Long> map = allWords.stream()
    .collect(groupingBy(Function.identity(), HashMap::new, counting()));
map.values().removeIf(l -> l<=2);
Set<String> commonlyUsed=map.keySet();

Note that in Java 8, HashSet still wraps a HashMap, so using the keySet() of a HashMap, when you want a Set in the first place, doesn’t waste space given the current implementation.

Of course, you can hide the post-processing in a Collector if that feels more “streamy”:

Set<String> commonlyUsed = allWords.stream()
    .collect(collectingAndThen(
        groupingBy(Function.identity(), HashMap::new, counting()),
        map-> { map.values().removeIf(l -> l<=2); return map.keySet(); }));
4
votes

A while ago I wrote an experimental distinct(atLeast) method for my library:

public StreamEx<T> distinct(long atLeast) {
    if (atLeast <= 1)
        return distinct();
    AtomicLong nullCount = new AtomicLong();
    ConcurrentHashMap<T, Long> map = new ConcurrentHashMap<>();
    return filter(t -> {
        if (t == null) {
            return nullCount.incrementAndGet() == atLeast;
        }
        return map.merge(t, 1L, (u, v) -> (u + v)) == atLeast;
    });
}

So the idea was to use it like this:

Set<String> commonlyUsed = StreamEx.of(allWords).distinct(3).toSet();

This performs a stateful filtration, which looks a little bit ugly. I doubted whether such feature is useful thus I did not merge it into the master branch. Nevertheless it does the job in single stream pass. Probably I should revive it. Meanwhile you can copy this code into the static method and use it like this:

Set<String> commonlyUsed = distinct(allWords.stream(), 3).collect(Collectors.toSet());

Update (2015/05/31): I added the distinct(atLeast) method to the StreamEx 0.3.1. It's implemented using custom spliterator. Benchmarks showed that this implementation is significantly faster for sequential streams than stateful filtering described above and in many cases it's also faster than other solutions proposed in this topic. Also it works nicely if null is encountered in the stream (the groupingBy collector doesn't support null as class, thus groupingBy-based solutions will fail if null is encountered).

0
votes

I personally prefer Holger's solution (+1), but, instead of removing elements from the groupingBy map, I would filter its entrySet and map the result to a Set in the finalizer (it feels even more streamy to me)

    Set<String> commonlyUsed = allWords.stream().collect(
            collectingAndThen(
                groupingBy(identity(), counting()), 
                (map) -> map.entrySet().stream().
                            filter(e -> e.getValue() > 2).
                            map(e -> e.getKey()).
                            collect(Collectors.toSet())));