13

一意であることが保証されているオブジェクトのコレクションがあります (特に、一意の整数 ID によってインデックスが付けられています)。私はまた、それらの数を正確に知っています (そしてその数は変わりません)。そして、Array が HashSet よりも、その要素を格納/取得する際に顕著なパフォーマンス上の利点があるかどうか疑問に思っていました。

紙の上では、Array は一定時間の挿入 (事前にサイズを知っているため) と取得を保証しますが、HashSet のコードははるかにきれいに見え、ある程度の柔軟性が追加されているので、それを使用するとパフォーマンス面で何かが失われるのではないかと考えています。 、少なくとも、理論的には。

4

4 に答える 4

2

選択は、それで何をしたいかによって大きく異なります。

それがあなたの質問に記載されている場合：

一意であることが保証されているオブジェクトのコレクションがあります (特に、一意の整数 ID によってインデックスが付けられています)。また、それらの数が正確にわかっています。

これが必要な場合は、どちらも必要ありません。Collectionには size() メソッドがあり、そのサイズを取得できます。これは、コレクション内にいくつあるかを意味します。

「オブジェクトのコレクション」の意味が実際にはコレクションではなく、さらに処理するためにオブジェクトを格納するコレクションのタイプを選択する必要がある場合は、さまざまな種類のコレクションについて、さまざまな機能と機能があることを知っておく必要があります。特性。

まず、公平な比較ができると思います。再割り当てを処理する必要がない Array の代わりに ArrayList を使用することを検討する必要があります。

次に、ArrayList と HashSet の選択になります。これは非常に簡単です。

リストまたはセットが必要ですか? これらは目的が異なります。リストはインデックス付きアクセスを提供し、反復はインデックス順に行われます。セットは主にデータの個別のセットを保持するためのものであり、その性質を考えると、インデックス付きアクセスはありません。

使用するリストまたはセットを決定したら、リスト/セットの実装を選択します。通常、リストの場合は ArrayList と LinkedList から選択しますが、セットの場合は HashSet と TreeSet のいずれかを選択します。

すべての選択は、そのデータのコレクションで何をしたいかによって異なります。それらは、異なるアクションで異なるパフォーマンスを発揮します。

たとえば、ArrayList のインデックス付きアクセスは O(1)、HashSet では (意味はありませんが) O(n)、(参考までに、LinkedList では O(n)、TreeSet では O(nlogn) です)。

新しい要素を追加するには、ArrayList と HashSet の両方が O(1) 操作です。中間に挿入すると、ArrayList では O(n) になりますが、HashSet では意味がありません。どちらも再割り当ての影響を受け、再割り当てには両方とも O(n) が必要です (HashSet は通常、再割り当てが遅くなります。これは、各要素のハッシュの計算が再び必要になるためです)。

コレクションに特定の要素が存在するかどうかを調べるには、ArrayList は O(n)、HashSet は O(1) です。

まだまだやれることはたくさんあるので、何がしたいのかわからないまま性能を議論しても意味がありません。

于 2013-09-18T07:44:08.040 に答える
0

理論的に、そしてSCJP6スタディガイドが言うように:D

配列はコレクションよりも高速であり、前述のように、ほとんどのコレクションは主に配列に依存しています (マップはコレクションとは見なされませんが、コレクション フレームワークに含まれています)。

要素のサイズが変わらないことを保証する場合、ルートオブジェクトを直接使用できるのに、オブジェクト上に構築されたオブジェクト（配列上に構築されたコレクション）に固執するのはなぜですか（配列）

于 2013-09-09T21:43:37.060 に答える
0

ID をカウントにマップする HashMap が必要なようです。特に、

HashMap<Integer,Integer> counts=new HashMap<Integer,Integer>();
counts.put(uniqueID,counts.get(uniqueID)+1);

このようにして、償却された O(1) の追加、保持、取得を取得します。基本的に、各オブジェクトに関連付けられた一意の ID を持つ配列は HashMap です。HashMap を使用すると、配列のサイズを管理する必要がなく、自分でキーを配列インデックスにマップする必要がなく、アクセス時間が一定であるという追加のボーナスが得られます。

于 2013-09-18T06:19:59.913 に答える