我刚刚完成了当前数据结构项目的主要部分，并正在努力收集统计数据。一项要求是记录 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();
}
这个运行时间太长而无法接受。有没有更有效的方法来对最终结构执行此操作？我可以在绘制地图时进行计数，但教授希望这些数字基于最终结构本身。
I just finished the main part of the current data structures project, and am working on collecting the statistics. One requirement is that a count of all the references within the TreeMap be recorded.
This Map contains a 31,000+ nodes where a String is mapped to a TreeSet of indeterminate size.
I need to traverse the map and keep a running count of the number of items in the set.
Originally my idea was this:
Set<String> keySet= lyricWords.keySet();
Iterator<String> iter= keySet.iterator();
String current= iter.next();
while (iter.hasNext){
runCount+= lyricWords.get(current).size();
}
The runtime for this is far too long to be acceptable. Is there a more efficient way to do this on the final structure? I could keep a count as the map is built, but the professor wants the numbers to be based on the final structure itself.
发布评论
评论（4）
我不知道。但是，您可能有不定循环。尝试：
I'm not sure. But, probably, you have infinitive loop. Try:
我认为在构建地图时保持计数没有问题。
最终计数将是正确的，并且您不必承担再次迭代整个过程的成本。
我认为树可以而且应该记录它的大小
I dont see a problem with keeping a count as the map is built.
The count will be correct at the end, and you wont have to incur the cost of iterating through the entire thing again.
I think that the tree can and should keep track of its size
这对您来说没有多大用处，因为这是您正在处理的作业，但这是一个示例，其中专门为将键映射到多个值而设计的数据结构显示了它比 Map< 好得多。 T，集合>。
Guava 的
Multimap集合类型会跟踪其包含的条目总数，所以如果您使用的是TreeMultimap而不是TreeMap> 您只需调用multimap.size ()即可获取您要查找的号码。顺便说一句，
Multimap实现存储了条目数量的运行总数，当向其中添加条目或从中删除条目时，该总数会更新。您也许可以通过对TreeMap进行子类化并包装添加到其中的TreeSet来完成一些奇特的事情，但是它我认为要让这一切正常工作将是相当具有挑战性的。This isn't of much use to you since this is an assignment you're working on, but this is an example where a data structure specifically designed for mapping keys to multiple values shows how much better it is than a
Map<T, Collection<V>>.Guava's
Multimapcollection type keeps track of the total number of entries it contains, so if you were using aTreeMultimap<String, Foo>rather than aTreeMap<String, TreeSet<Foo>>you could just callmultimap.size()to get the number you're looking for.By the way, the
Multimapimplementations store a running total of the number of entries which is updated when entries are added to or removed from it. You might be able to do this by doing some fancy stuff with subclassing theTreeMapand wrapping theTreeSets that are added to it, but it would be quite challenging to make it all work properly I think.