Найти лучшие десять значений на карте - PullRequest
2 голосов
/ 10 ноября 2010

Скажем, у меня есть TreeMap<String, Treeset<Song>>, где объект Song имеет три поля String и внутренний метод CompareTo.Ключи для карты - это уникальные слова в тексте, которые не являются общими словами, такими как «она», «the», «if» или «on».На карте имеется несколько копий песен, поскольку в среднем на одну песню отображается в среднем 60 слов.

Для дополнительной оценки профессор попросил нас придумать алгоритм для поиска 10 лучших значений.на карте.Я не решил проблему вовремя, вот почему я спрашиваю здесь.

Часть, на которой я поставлен, в отличие от упорядоченного массива или списка, вы не можете просто взятьверхние значения последовательно.Итак, я подумал о:

Create a PriorityQueue<Node> with the Comparator sorting the Nodes based
on the Set size

iterate over the map
   for each map node
     create a Node object with the key-value pair
     insert Node into the queue

Несмотря на то, что в PriorityQueue будут все пары ключ-значение, верхние размеры будут наверху, и я могу просто получить первые десять.

Это кажется очень окольным путем, так как эта конкретная карта имеет более 31 000 узлов, отображающих более 637 000 значений.Есть ли лучший способ?

Ответы [ 2 ]

1 голос
/ 10 ноября 2010

Простая модификация вашего алгоритма:

Create a PriorityQueue<Node> with the Comparator sorting the Nodes based
on the Set size

iterate over the map
  for each map node
    if value for node is larger than last entry in priority queue
      create a Node object with the key-value pair
      insert Node into the queue
      trim the queue to ten entries

По завершении очередь с приоритетами будет содержать только первые 10 записей.

0 голосов
/ 10 ноября 2010

Я не уверен, что вам нужны первые 10 по ключу, и в этом случае Soldier.moth прав, и вы можете получить нисходящее представление, вызывающее downndingMap, а затем выполнить итерацию для первых 10 элементов. Но если вы хотите получить 10 лучших по каким-то другим отношениям, просто итерируйте по elementSet и сохраните текущие 10 лучших в отсортированной структуре данных, как TreeSet, определяющий компаратор на основе размера - не уверен, какой размер вы имеете в виду, но вы, вероятно, знаете - - и для каждого элемента вы заменяете наименьшее из 10, если оно меньше текущего. Вы получаете наименьшее с firstKey

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...