Suche nach Top N Elemente in einem Multiset von Google-Sammlungen?

Question

Google Sammlungen Multiset eine Reihe von Elementen, von denen jedes einen Zählwert hat (dh kann vorhanden sein, mehrfach).

Ich kann Ihnen nicht sagen, wie oft ich die folgenden

tun will

1. Erstellen Sie ein Histogramm (genau Multiset)
2. Holen Sie sich die Top-N Elemente durch Zählung aus dem Histogramm

Beispiele: Top 10 der URLs (von # Nennungen), Top-10-Tags (von # Mal angewendet wird), ...

Was ist der kanonische Weg # 2 gegeben ein Google Sammlung Multiset?

zu tun

Hier ist eine Blog-Post darüber, aber dieser Code ist nicht ganz das, was ich will. Erstens, es gibt alles, nicht nur N. Second oben, kopiert es (ist es möglich, eine Kopie zu vermeiden?). Drittens möchte ich in der Regel eine deterministische Art, das heißt, wenn Tie-Break zählt gleich sind. Andere nits. Es ist nicht statisch, etc

Answer 1

Ich schrieb Methoden mit den grundlegenden Funktionen, nach dem Sie fragen, mit der Ausnahme, dass sie Kopien durchführen und es fehlt ihnen determinis tie-breaking Logik. Sie sind zur Zeit intern zu Google, aber wir können Open-Source sie an einem gewissen Punkt. Diese Guava Ausgabe hat die Methodensignaturen.

Ihr Algorithmus ist ähnlich dem Blog-Eintrag: eine Liste von Einträgen zu sortieren. Es wäre schneller, aber mehr kompliziert, um eine bessere zu verwenden Auswahlalgorithmus .

EDIT: da Guava 11, das ist implementiert

Answer 2

Um eine andere Perspektive geben für die Menschen zu kommentieren, ich werde eine leicht modifizierte Version des Blog-Post Ich poste verwiesen:

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;
    }
}