Найти вершину N элементами в Мультимножестве от Google Collections?
Наборы Google Мультимножество является рядом элементов, каждый из которых имеет количество (т.е. может присутствовать многократно).
Я не могу сказать Вам, сколько раз я хочу сделать следующее
- Сделайте гистограмму (точно Мультимножество)
- Получите вершину N элементы количеством от гистограммы
Примеры: лучшие 10 URL (к # упомянутым временам), лучшие 10 тегов (к # примененным временам)...
Что канонический путь состоит в том, чтобы сделать № 2, учитывая Google Collections Multiset?
Вот сообщение в блоге об этом, но тот код не совсем, что я хочу. Во-первых, это возвращает все, не просто вершину N. Во-вторых, это копирует (действительно ли возможно избежать копии?). В-третьих, я обычно хочу детерминированный вид, т.е. тай-брейк, если количества равны. Другие гниды: это не статично и т.д.
2 ответа
Я написал методы с базовой функциональностью, которую вы запрашиваете, за исключением того, что они выполняют копии и не имеют детерминированной логики разрыва связей. В настоящее время они являются внутренними для Google, но в какой-то момент мы можем открыть их исходный код. Эта проблема Guava имеет сигнатуры методов.
Их алгоритм похож на запись в блоге: сортировка списка записей. Было бы быстрее, но сложнее использовать лучший алгоритм выбора .
РЕДАКТИРОВАТЬ: начиная с Guava 11, это реализовано
Чтобы дать людям другую перспективу для комментариев, я опубликую немного измененную версию сообщения в блоге, на которое я ссылался:
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;
}
}