11
\$\begingroup\$

Some very common tasks that keep popping up from time time:

  • Find the most frequent something in a collection of things
  • ... or the count of that thing
  • ... or both (the item and its count)
  • Get the list of distinct items, with their counts, sorted by their counts
  • Get the N most frequent items, with their counts

To avoid typing up the same kind of frequency counting code over and over again, I came up with this:

public class FrequencyCounter<T> {

    private final Map<T, Integer> frequencyMap = new HashMap<>();

    private final Comparator<T> countComparator = (o1, o2) -> Integer.compare(frequencyMap.get(o1), frequencyMap.get(o2));

    public void add(T item) {
        Integer count = frequencyMap.get(item);
        if (count == null) {
            count = 0;
        }
        frequencyMap.put(item, count + 1);
    }

    public void addAll(Collection<T> items) {
        items.forEach(this::add);
    }

    public T getMostFrequentItem() {
        return toSortedMap().lastKey();
    }

    public int getMostFrequentCount() {
        SortedMap<T, Integer> sortedMap = toSortedMap();
        T lastKey = sortedMap.lastKey();
        return sortedMap.get(lastKey);
    }

    private SortedMap<T, Integer> toSortedMap(Comparator<T> comparator) {
        SortedMap<T, Integer> sortedMap = new TreeMap<>(comparator);
        sortedMap.putAll(frequencyMap);
        return sortedMap;
    }

    public SortedMap<T, Integer> toSortedMap() {
        return toSortedMap(countComparator);
    }

    public SortedMap<T, Integer> toReversedMap() {
        return toSortedMap(Collections.reverseOrder(countComparator));
    }

    private List<T> toSortedList(Comparator<T> comparator) {
        List<T> list = new ArrayList<>(frequencyMap.keySet());
        Collections.sort(list, comparator);
        return list;
    }

    public List<T> toSortedList() {
        return toSortedList(countComparator);
    }

    public List<T> toReversedList() {
        return toSortedList(Collections.reverseOrder(countComparator));
    }
}

Unit tests:

public class FrequencyCounterTest {
    @Test
    public void test_getMostFrequentItem() {
        FrequencyCounter<Integer> counter = new FrequencyCounter<>();
        counter.addAll(Arrays.asList(1, 4, 9, 3, 4, 5, 4, 9));
        assertEquals(new Integer(4), counter.getMostFrequentItem());
    }

    @Test
    public void test_getMostFrequentCount() {
        FrequencyCounter<Integer> counter = new FrequencyCounter<>();
        counter.addAll(Arrays.asList(1, 4, 9, 3, 4, 5, 4, 9));
        assertEquals(3, counter.getMostFrequentCount());
    }

    @Test
    public void test_getMostFrequentLetter() {
        FrequencyCounter<Character> counter = new FrequencyCounter<>();
        String text = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, " +
                "sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. " +
                "Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris " +
                "nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in " +
                "reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla " +
                "pariatur. Excepteur sint occaecat cupidatat non proident, sunt in " +
                "culpa qui officia deserunt mollit anim id est laborum.";

        for (char c : text.replace(" ", "").toCharArray()) {
            counter.add(c);
        }
        assertEquals(new Character('i'), counter.getMostFrequentItem());
    }

    @Test
    public void test_map_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("{hello=1, hi=2}", counter.toSortedMap().toString());
    }

    @Test
    public void test_map_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("{hello=1, hi=2}", counter.toSortedMap().toString());
    }

    @Test
    public void test_map_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("{hi=2, hello=3}", counter.toSortedMap().toString());
    }

    @Test
    public void test_sortedList_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("[hello, hi]", counter.toSortedList().toString());
    }

    @Test
    public void test_sortedList_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("[hello, hi]", counter.toSortedList().toString());
    }

    @Test
    public void test_sortedList_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("[hi, hello]", counter.toSortedList().toString());
    }

    @Test
    public void test_reversedList_hi_hi_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        assertEquals("[hi, hello]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        assertEquals("[hi, hello]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi_hello_hello() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        assertEquals("[hello, hi]", counter.toReversedList().toString());
    }

    @Test
    public void test_reversedList_hello_hi_hi_hello_hello_null() {
        FrequencyCounter<String> counter = new FrequencyCounter<>();
        counter.add("hello");
        counter.add("hi");
        counter.add("hi");
        counter.add("hello");
        counter.add("hello");
        counter.add(null);
        assertEquals("[hello, hi, null]", counter.toReversedList().toString());
    }
}

What do you think?

  • Anything to improve, or odd-looking?
  • Am I reinventing the wheel? Is there something existing that I can use instead?
  • Is this usable, ergonomic enough, or can it be better?
\$\endgroup\$
  • 1
    \$\begingroup\$ Have you considered Java 8 streams? These kind of tasks are quite well-suited for streams and lambdas... \$\endgroup\$ – h.j.k. Mar 5 '15 at 1:24
3
\$\begingroup\$

@Simon has a good answer about some usability issues, but I want to focus on the performance and memory aspects of it.

I agree with Simon that the counter should be a long value, but, more than that, you should create a mutable long class, and not use Long (or, in your case, Integer).

Consider the class:

public class Counter (

    private long count = 0;

    public long increment() {
        return ++count;
    }

    public long get() {
        return count;
    }
}

Now, create your internal map as:

private final Map<T, Counter> frequencyMap = new HashMap<>();

In your add() method, have:

public void add(T item) {
    frequencyMap.computeIfAbsent(item, k -> new Counter()).increment();
}

By using a counter, you greatly reduce the amount of memory churn in your map, and you can convert it easily to a reportable Long instance when you externalize the values.

\$\endgroup\$
5
\$\begingroup\$

Stream, Stream, Stream

It seems to be quite common to create a FrequencyCounter from a Collection, so why not make it a static factory method?

public static <T> FrequencyCounter<T> fromCollection(Collection<T> values) {
    FrequencyCounter<T> result = new FrequencyCounter<>();
    result.addAll(values);
    return result;
}

Or, if you switch the Map<T, Integer> to Map<T, Long>, how about from a Stream, using some Stream magic?

private FrequencyCounter(Map<T, Long> frequencyMap) {
    this.frequencyMap = frequencyMap;
    this.countComparator = (o1, o2) -> Long.compare(frequencyMap.get(o1), frequencyMap.get(o2));
}

public static <T> FrequencyCounter<T> fromStream(Stream<T> stream) {
    Map<T, Long> frequencies = stream.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
    return new FrequencyCounter<>(frequencies);
}

I believe this line is about as close to an already-existing wheel as you are going to get:

Map<T, Long> frequencies = stream.collect(Collectors.groupingBy(e -> e, Collectors.counting()));

In your test_getMostFrequentLetter you can then do:

counter = FrequencyCounter.fromStream(text.chars().filter(i -> i != ' ')
    .mapToObj(i -> (char) i));

And in another test:

FrequencyCounter<String> counter = FrequencyCounter.fromStream(Stream.of("hi", "hi", "hello"));

Stream, Stream, Stream, all you have to do, is Stream...

Immutability?

Consider making FrequencyCounter immutable, or having a separate FrequencyCount that simply holds the result from the FrequencyCounter (then you'd also just have to call toSortedMap once)

Adding is merging

Your add method can be quite simplified when using merge:

public void add(T item) {
    frequencyMap.merge(item, 1L, (oldValue, value) -> oldValue + value);
}

Get methods

Let's take a look at your get methods...

public T getMostFrequentItem()
public int getMostFrequentCount()
public SortedMap<T, Integer> toSortedMap()
public SortedMap<T, Integer> toReversedMap()
public List<T> toSortedList()
public List<T> toReversedList()

How about int getFrequency(T item) ?

Or some other way to access the already existing Map<T, Long> without the overhead of turning it into a SortedMap ?

Edge case

Consider this code:

FrequencyCounter<String> counter = new FrequencyCounter<>();
String mostUsed = counter.getMostFrequentItem();
int count = counter.getMostFrequentCount();

This will cause 2x NullPointerException. There is no most frequent item. There is no most frequent count.

I would expect counter.getMostFrequentCount() to return 0 in this case, and I'd probably make counter.getMostFrequentItem() return null. Either way, it is an edge-case that I don't think you have considered. It's up to you how you will handle it :)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.