Find top N elements in a Multiset from Google Collections?

Question

A Google Collections Multiset is a set of elements each of which has a count (i.e. may be present multiple times).

I can't tell you how many times I want to do the following

1. Make a histogram (exactly Multiset)
2. Get the top N elements by count from the histogram

Examples: top 10 URLs (by # times mentioned), top 10 tags (by # times applied), ...

What is the canonical way to do #2 given a Google Collections Multiset?

Here is a blog post about it, but that code is not quite what I want. First, it returns everything, not just top N. Second, it copies (is it possible to avoid a copy?). Third, I usually want a deterministic sort, i.e. tiebreak if counts are equal. Other nits: it's not static, etc.

Answer 1

To give another perspective for people to comment on, I'll post a slightly modified version of the blog post I referenced:

package com.blueshiftlab.twitterstream.summarytools;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Multiset;
import com.google.common.collect.Ordering;
import com.google.common.collect.Multiset.Entry;

public class Multisets {
    // Don't construct one
    private Multisets() {
    }

    public static <T> ImmutableList<Entry<T>> sortedByCount(Multiset<T> multiset) {
        Ordering<Multiset.Entry<T>> countComp = new Ordering<Multiset.Entry<T>>() {
            public int compare(Multiset.Entry<T> e1, Multiset.Entry<T> e2) {
                return e2.getCount() - e1.getCount();
            }
        };
        return countComp.immutableSortedCopy(multiset.entrySet());
    }

    public static <T> ImmutableList<Entry<T>> topByCount(Multiset<T> multiset,
            int max) {
        ImmutableList<Entry<T>> sortedByCount = sortedByCount(multiset);
        if (sortedByCount.size() > max) {
            sortedByCount = sortedByCount.subList(0, max);
        }

        return sortedByCount;
    }
}

Answer 2

I wrote methods with the basic functionality you're asking for, except that they perform copies and lack deterministic tie-breaking logic. They're currently internal to Google, but we may open-source them at some point. This Guava issue has the method signatures.

Their algorithm is similar to the blog post: sorting a list of entries. It would be faster, but more complicated, to use a better selection algorithm.