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

Question

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

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

Или мне было бы лучше просто использовать хэш-карту и отсортировать ее по значению, как описано, например, в Java-сортировка HashMap по значению

Answer 1

С Гуавы TreeMultiset, просто используйте Multisets.copyHighestCountFirst.

Answer 2

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

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