Компаратор для TreeBag для сортировки по количеству вхождений

Question

У меня есть источник строк (скажем, текстовый файл), и многие строки повторяются несколько раз. Мне нужно получить верхние X наиболее распространенных строк в порядке уменьшения количества вхождений.

Идея, что пришло на ум первым должен был создать Сортируемый мешок (что-то вроде org.apache.commons.collections.bag.TreeBag) и поставить компаратор, который будет сортировать записи в порядке, мне нужно. Однако я не могу понять, какой тип объектов мне нужно сравнить. Это должна быть какая-то внутренняя карта, которая объединяет мой объект (String) и количество вхождений, сгенерированных внутри TreeBag. Это возможно?

Или мне лучше просто используя HashMap и сортировать его по значению, как описано, например, Java sort HashMap by value

Answer 1

Почему вы не поставить струны на карте. Карта строки в количестве раз, когда они появляются в тексте. На шаге 2 перемещайте элементы на карте и продолжайте добавлять их к минимальной куче размера X. Всегда извлекайте сначала мин, если куча заполнена перед вставкой.
Принимает время nlogx.

В противном случае после шага 1 сортировать предметы по количеству вхождений и брать первые х предметов. Здесь будет полезной карта деревьев :) (я бы добавил ссылку на javadocs, но я на планшете) Принимает время nlogn.

Answer 2

С Guava'sTreeMultiset, просто используйте Multisets.copyHighestCountFirst.