0

我刚刚完成了当前数据结构项目的主要部分，并且正在收集统计数据。一个要求是记录 TreeMap 中所有引用的计数。

此 Map 包含 31,000 多个节点，其中 String 映射到大小不确定的 TreeSet。我需要遍历地图并保持对集合中项目数量的运行计数。

最初我的想法是这样的：

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

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

运行时间太长而无法接受。有没有更有效的方法在最终结构上做到这一点？我可以在地图构建时进行计数，但教授希望这些数字基于最终结构本身。

4

4 回答 4

3

我不知道。但是，可能你有不定式循环。尝试：

runCount+= iter.next().size();
于 2010-11-04T20:09:47.437 回答
3 
for (Map.Entry<String, TreeSet> e: lyricWords.entrySet()) {
  runCount+= e.getValue().size();
}
于 2010-11-04T20:12:43.790 回答
1

在地图构建时，我认为保持计数没有问题。

最后计数将是正确的，并且您不必承担再次遍历整个事物的成本。

我认为这棵树可以而且应该跟踪它的大小

于 2010-11-04T20:09:28.313 回答
0

这对您没有多大用处，因为这是您正在处理的任务，但这是一个示例，其中专门设计用于将键映射到多个值的数据结构显示它比Map<T, Collection<V>>.

Guava的Multimap集合类型会跟踪它包含的条目总数，因此如果您使用的是 aTreeMultimap<String, Foo>而不是 a ，则TreeMap<String, TreeSet<Foo>>可以调用multimap.size()以获取您要查找的数字。

顺便说一句，Multimap实现存储了条目数的运行总数，当条目被添加到条目或从中删除时，条目数会更新。您可以TreeMap通过对添加到其中的 s 进行子类化和包装s来做一些花哨的事情来做到这TreeSet一点，但是我认为要使其全部正常工作将非常具有挑战性。

于 2010-11-04T20:25:52.427 回答