5

項目の順序を指定して、java.util.Collection への挿入速度を最適化する方法はありますか?

例えば

java.util.Set<String> set = java.util.TreeSet<String>();

この解決策は次のとおりです。

set.add("A");
set.add("B");
set.add("C");
set.add("D");
set.add("E");

これよりも速くなりますか (順不同) ?

set.add("E");
set.add("D");
set.add("C");
set.add("A");
set.add("B");

(そして、他のコレクションについても同じ質問: HashMap、hastable...)

ありがとう

4

5 に答える 5

8

簡単な答えは、「時間を取って見てください」です。

もう1つの答えは、「問題ありません」です。これは、努力する価値がほとんどないマイクロ最適化のようです。「マイクロ最適化劇場の悲しい悲劇」の部類に入ると思います。

于 2009-02-22T18:11:33.520 に答える
6

java.util.Map と java.util.Set はいいえ。これらはインターフェイスであり、実装が異なるためです。

具体的な実装では、価値のある最適化ではありません。パフォーマンスに問題がある場合は、より適切な実装を選択するか、何をどのように格納する必要があるかを再考してください。

HashSet に 5000 個の乱数を挿入するには、ありふれたラップトップで約 1 ミリ秒かかります。

于 2009-02-22T18:15:37.440 に答える
3

赤黒木(Java のTreeSet/TreeMapの実装に使用される) の挿入時間は、最悪の場合で O(log n) になることが保証されています。アイテムが特定の順序になっている場合は高速になる可能性がありますが、それが何であるかはわかりません (おそらく、事前に並べ替えた方が最速でしょうか?)。

ハッシュテーブルへの挿入は、O(1) (一定時間) 操作です。挿入のために行われる主なことは、ハッシュコードの計算です。

編集: Starblue は、事前にソートすると最悪の場合のパフォーマンスが得られる可能性があることを示唆しているため、ランダム化された順序を試すことができます。

于 2009-02-22T18:11:16.437 に答える
2

当然、ハッシュベースのコレクションとツリーベースのコレクションの間には大きな違いがあります。

ツリーベースのものは、挿入のための要素の順序付け (文字列間の比較など) の恩恵を受けるため、比較可能なオブジェクト (文字列など) がある場合は、それらを使用することをお勧めします。TreeSet/TreeMap/etc. 標準コレクションではバランスがとれている (赤黒木) はずなので、挿入順序はそれほど重要ではありません。バランスが取れていないと、ツリーではなくチェーンになってしまう可能性があるため、挿入順序が重要になります。

ハッシュ テーブルでは、読み込み係数とハッシュ関数がすべてを決定しますが、文字列を扱っている場合は、ハッシュを気にしない方がよい場合もあります。

オーバーラップのある多くの文字列に対して一連の文字列が必要な場合は、Trie の方がメモリ効率が良いかもしれませんが、ライブラリにはないと思います。

于 2009-02-22T18:14:03.157 に答える
1

最適化の手段を講じるときは、データ構造の特性を慎重に検討してください。1 つの極端な例として、ソートされた順序でバイナリ ツリーに要素を挿入すると、連結リストが作成されます。

于 2009-02-22T18:53:14.310 に答える