How to get Top N values based on repetition from a list in Java

user_1048486 0
Viewed 100

I am trying to get Top N values based on repetition from a list in Java.

Example: Find Top 2 values
[ "strawberries", "orange", "apple", "mango", "grapes", "pineapple", "mango", "strawberries", "mango", "apple"]

Result:
["mango"] //mango repeated 3 times
["strawberries", "apple"] // "strawberries", "apple" repeated 2 times each

I have written below code to acheive this

private static List<List<String>> getTop(int n, List<String> values) {

    Map<String, Long> valueCountMap = values.stream()
                           .collect(groupingBy(x -> x, counting()));

    final Map<String, Long> sortedByCount = valueCountMap.entrySet()
            .stream()
            .sorted(Map.Entry.<String, Long>comparingByValue().reversed())
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (x, y) -> y, LinkedHashMap::new));

    List<List<String>> topNValues = new ArrayList<>();
    long prevValue = -1;
    for (Map.Entry<String, Long> e : sortedByCount.entrySet()) {
        if (prevValue == -1 || prevValue != e.getValue()) {
            if (topNValues.size() == n) {
                break;
            }
            prevValue = e.getValue();
            List<String> keys = new ArrayList<>();
            keys.add(e.getKey());
            topNValues.add(keys);
        } else if (prevValue == e.getValue()) {
            List<String> keys = topNValues.get(topNValues.size() - 1);
            keys.add(e.getKey());
        }
    }

    return topNValues;
}

I want to know if there is a better way of implementing this. Both performance and implementation wise.

java-stream sorting algorithm java
2 Answers

Try this.

private static List<List<String>> getTop(int n, List<String> values) {
    return values.stream()
        .collect(Collectors.groupingBy(s -> s, Collectors.counting()))
        .entrySet().stream()
        .collect(Collectors.groupingBy(Entry::getValue,
            TreeMap::new,
            Collectors.mapping(Entry::getKey, Collectors.toList())))
        .descendingMap().values().stream()
        .limit(n)
        .collect(Collectors.toList());
}

Input

[strawberries, orange, apple, mango, grapes, pineapple, mango, strawberries, mango, apple]

Result of first .collect().

{orange=1, apple=2, pineapple=1, strawberries=2, grapes=1, mango=3}

Result of second .collect().

{1=[orange, pineapple, grapes], 2=[apple, strawberries], 3=[mango]}

Result of .descendingMap()

{3=[mango], 2=[apple, strawberries], 1=[orange, pineapple, grapes]}

Result of last .collect()

[[mango], [apple, strawberries]]
Admin1

What you seem to be looking for is really a List<Set<String>> as an output. A simplification to is possible if you have ranked entries based on the counting you've performed to start off with:

private static List<Set<String>> getTopN(int n, List<String> values) {
    Map<String, Long> valueCountMap = values.stream()
            .collect(Collectors.groupingBy(x -> x, Collectors.counting()));

    Map<Long, Set<String>> rankedEntries = values.stream()
            .collect(Collectors.groupingBy(valueCountMap::get, Collectors.toSet()));

    return rankedEntries.entrySet().stream()
            .sorted(Map.Entry.<Long, Set<String>>comparingByKey().reversed())
            .limit(n)
            .map(Map.Entry::getValue)
            .collect(Collectors.toList());
}

In terms of performance, you already have a decent algorithm to obtain the result. In the above solution for a input of N elements, this would iterate N times for counting, then N times performs a lookup on the frequency map and later iterate rankedEntries which is always < N, so you would end up with the complexity of O(N) overall.

user_17461180
Related