0

現在のデータ構造プロジェクトの主要部分を終えたばかりで、統計の収集に取り組んでいます。1 つの要件は、TreeMap 内のすべての参照のカウントを記録することです。

この Map には、String が不定サイズの TreeSet にマップされる 31,000 以上のノードが含まれています。マップを横断して、セット内のアイテム数を継続的にカウントする必要があります。

もともと私の考えはこれでした：

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実装は、エントリが追加または削除されたときに更新されるエントリ数の現在の合計を保存します。をサブクラス化し、それに追加されたをラップすることで、これを行うことができるかもしれませんが、すべてを適切に機能させるのは非常に難しいと思います。TreeMapTreeSet

于 2010-11-04T20:25:52.427 に答える