Есть ли лучший способ рассчитать значения на карте?

Question

Я только что закончил основную часть текущего проекта структур данных и работаю над сбором статистики.Одно требование состоит в том, чтобы было подсчитано количество всех ссылок в TreeMap.

Эта карта содержит более 31 000 узлов, где строка сопоставляется с TreeSet неопределенного размера.Мне нужно пересечь карту и вести подсчет количества предметов в наборе.

Первоначально моя идея заключалась в следующем:

Set<String> keySet= lyricWords.keySet();  
Iterator<String> iter= keySet.iterator();
String current= iter.next();

while (iter.hasNext){
  runCount+= lyricWords.get(current).size();
}

Время выполнения для этого слишком долго, чтобыбыть приемлемым.Есть ли более эффективный способ сделать это в окончательной структуре?Я мог бы вести подсчет по мере построения карты, но профессор хочет, чтобы числа основывались на самой окончательной структуре.

Answer 1

Я не уверен.Но, возможно, у вас есть бесконечный цикл.Попробуйте:

runCount+= iter.next().size();

Answer 2

for (Map.Entry<String, TreeSet> e: lyricWords.entrySet()) {
  runCount+= e.getValue().size();
}

Answer 3

Я не вижу проблемы с подсчетом при построении карты.

Счет будет правильным в конце, и вам не придется нести расходы на повторение всей вещи снова.

Я думаю, что дерево может и должно отслеживать его размер

Answer 4

Это не очень полезно для вас, так как это задание, над которым вы работаете, но это пример, где структура данных, специально разработанная для сопоставления ключей с несколькими значениями, показывает, насколько она лучше, чем * 1001. *.

Тип сбора Guava Multimap отслеживает общее количество записей, которые он содержит, поэтому, если вы используете TreeMultimap<String, Foo> вместо TreeMap<String, TreeSet<Foo>>, вы можете просто позвонить multimap.size() чтобы получить номер, который вы ищете.

Кстати, реализации Multimap хранят промежуточную сумму количества записей, которая обновляется, когда записи добавляются или удаляются из нее. Вы могли бы быть в состоянии сделать это, выполнив некоторые причудливые вещи с подклассами TreeMap и упаковав добавленные к нему TreeSet, но было бы довольно сложно заставить все это работать должным образом. думаю.