5

ArrayがCollectionよりも優れている理由をパフォーマンスに関して教えてください。

4

5 に答える 5

7

そうではない。実際には、コンテナの使用方法によって異なります。

一部のアルゴリズムは、配列では O(n) で実行され、別のコレクション型 ( Collection インターフェースを実装する) では O(1) で実行される場合があります。

  • たとえば、アイテムの削除について考えてみましょう。その場合、配列は、ネイティブ型であっても、リンクされたリストとそのメソッド呼び出し (一部の VM ではいずれにせよインライン化される可能性があります) よりもパフォーマンスが低下します。リスト
  • 要素の検索について考えてみましょう。配列の場合は 0(n)、ツリーの場合は O(log n) で実行されます。

一部の Collection 実装は、配列を使用して要素を格納するため (ArrayList だと思います)、その場合、パフォーマンスに大きな違いはありません。

配列 VS コレクションの長所/短所を心配するのではなく、アルゴリズムの最適化 (および利用可能なさまざまなコレクション タイプの利用) に時間を費やす必要があります。

于 2012-12-17T08:15:42.393 に答える
3

多くのコレクションは配列のラッパーです。これには、ArrayList、HashMap / Set、StringBuilderが含まれます。最適化されたコードの場合、そのデータ構造により適した操作を行う場合を除いて、操作のパフォーマンスの違いは最小限です。たとえば、マップのルックアップは配列のルックアップよりもはるかに高速です。

基本的にプリミティブであるコレクションにジェネリックを使用すると、コレクションが遅くなるためではなく、余分なオブジェクトの作成とキャッシュの使用量が遅くなる可能性があります（必要なメモリが多くなる可能性があるため）。オブジェクトの配列の代わりに、プリミティブの配列のラッパーであるTrove4Jライブラリを使用できます。

コレクションの速度が遅いのは、LinkedListのランダムアクセスなどに適さない操作を使用する場合ですが、適切なコーディングによってこれらの状況を回避できます。

于 2012-12-17T08:28:37.880 に答える
1

基本的に、配列はJavaのプリミティブデータ構造であるためです。それらへのアクセスは、メソッド呼び出しではなく、ネイティブのメモリアクセス命令に直接変換できます。

とはいえ、すべての状況で配列がコレクションよりも厳密に優れていることは完全には明らかではありません。コードが実行時型をJIT時に単形的に知ることができるコレクション変数を参照する場合、Hotspotはアクセスメソッドをインライン化でき、それらが単純な場合は、基本的にオーバーヘッドがないため、同じくらい高速になります。

ただし、コレクションのアクセス方法の多くは、配列参照よりも本質的に複雑です。たとえば、HashMapHotspotがどれだけ最適化しても、単純な配列ルックアップほど効率的になる方法はありません。

于 2012-12-17T08:19:51.327 に答える
0

問題は、どれをいつ使用するかです。

配列は、基本的に要素の固定サイズのコレクションです。配列の悪い点は、サイズを変更できないことです。ただし、要素のサイズが明確な場合、その一定のサイズは効率的です。したがって、利用可能な要素の数がわかっている場合は、配列を使用することをお勧めします。

コレクション

ArrayListは、要素数のサイズを変更できる別のコレクションです。したがって、コレクション内の要素数がわからない場合は、ArrayList を使用してください。ただし、ArrayLists を使用する際に考慮すべき特定の事実があります。

  • ArrayLists は同期されません。そのため、複数のスレッドがリストにアクセスしてリストを変更している場合、同期を外部で処理する必要がある場合があります。

  • ArrayList は内部的に配列として実装されています。したがって、新しい要素が追加されるたびに、n+1 要素の配列が作成され、n 個の要素すべてが古い配列から新しい配列にコピーされ、新しい要素が新しい配列に挿入されます。

  • n 個の要素を追加するには、時間通りに行う必要があります。

  • isEmpty、size、iterator、set、get、および listIterator 操作に
    は、アクセスする要素に関係なく、同じ時間が必要です。

  • ArrayList に追加できるのはオブジェクトのみです

  • null 要素を許可する

ArrayList に多数の要素を追加する必要がある場合は、ensureCapacity(int minCapacity) 操作を使用して、ArrayList に必要な容量があることを確認できます。これにより、すべての要素が追加されたときに Array が 1 回だけコピーされるようになり、ArrayList への要素の追加のパフォーマンスが向上します。また、たとえば 1000 個の要素の真ん中に要素を挿入するには、500 個の要素を上下に移動してから、要素を真ん中に追加する必要があります。

ArrayList を使用する利点は、ランダムな要素へのアクセスが安価であり、ArrayList 内の要素の数に影響されないことです。しかし、尾の頭や途中に要素を追加するにはコストがかかります。

Vectorは ArrayList と似ていますが、同期されている点が異なります。初期容量と増分容量があるなど、他にもいくつかの利点があります。したがって、ベクターの容量が 10 で増分容量が 10 の場合、11 番目の要素を追加すると、20 の要素を持つ新しいベクターが作成され、11 の要素が新しいベクターにコピーされます。したがって、12 番目から 20 番目の要素を追加しても、新しいベクトルを作成する必要はありません。

デフォルトでは、ベクトルがより多くの要素を保持するために内部データ構造のサイズを拡大する必要がある場合、内部データ構造のサイズは 2 倍になりますが、ArrayList の場合、サイズは 50% しか増加しません。したがって、ArrayList はスペースに関してより保守的です。

LinkedListははるかに柔軟で、コレクションの両側から要素を挿入、追加、および削除できます。キューとして、さらには両端キューとしても使用できます! 内部的には、LinkedList は配列を使用しません。LinkedList は、二重にリンクされた一連のノードです。各ノードには、実際にオブジェクトが格納されるヘッダーと、次または前のノードへの 2 つのリンクまたはポインターが含まれます。LinkedList は、互いに手を取り合っている人々で構成されるチェーンのように見えます。そのチェーンに人またはノードを挿入したり、削除したりできます。リンクされたリストを使用すると、リスト内の任意の時点でノードの挿入/削除操作を一定時間で実行できます。

そのため、リンクされたリスト (先頭、末尾、または中間) に要素を挿入することは、高価ではありません。また、ヘッドから要素を取得する場合も安価です。しかし、リンクされたリストの要素にランダムにアクセスしたり、リストの末尾にある要素にアクセスしたりする場合、操作は重くなります。n+1 番目の要素にアクセスするには、最初の n 要素を解析して n+1 番目の要素に到達する必要があります。

また、リンクされたリストは同期されません。そのため、リストを変更および読み取る複数のスレッドを外部で同期する必要があります。

したがって、リストの作成に使用するクラスの選択は、要件によって異なります。ArrayList または Vector( 同期が必要な場合 ) は、リストの最後に要素を追加し、要素にランダムにアクセスする必要がある場合に使用できます。追加操作よりもアクセス操作が多くなります。一方、リストの先頭または途中から多くの追加/削除 (要素) 操作を行う必要があり、アクセス操作が比較的少ない場合は、LinkedList を使用する必要があります。

于 2012-12-17T08:26:28.257 に答える
0

この 2 つを比較することはできません。ArrayList は実装、Collection はインターフェイスです。Collection インターフェースには異なる実装が存在する場合があります。

実際には、データへの単純なアクセスとして実装が選択されます。すべての要素をループする必要がある場合は、通常 ArrayList を使用します。キーによるアクセスが必要な場合はハッシュテーブル。

パフォーマンスは、測定が行われた後でのみ考慮する必要があります。コレクション フレームワークには Collection インターフェイスのような共通のインターフェイスがあるため、実装を簡単に変更できます。

于 2012-12-17T08:25:45.043 に答える