24

ApacheTreeListドキュメントから取得：

次の相対的なパフォーマンス統計は、このクラスを示しています。

             get  add  insert  iterate  remove
 TreeList       3    5       1       2       1
 ArrayList      1    1      40       1      40
 LinkedList  5800    1     350       2     325

それは続けて言う：

LinkedList実装の良い選択になることはめったにありません。TreeListわずかに多くのメモリを使用しますが、ほとんどの場合、これは適切な代替品です。

私の質問は次のとおりです。

  • ArrayList add、、、 insertおよびremove回の粉砕 とは何LinkedListですか？たとえば、実際の挿入と削除のケースが非常に有利であると期待する必要がありArrayListますか？

  • これはTreeList単に由緒ある人の棺に釘を入れるだけLinkedListですか？

私は、彼らが成長する痛みを償却または無視したと結論付けたいと思います。そして、すでにArrayList見つけられたアイテムの挿入と取り外しの時間を考慮していません。LinkedList

4

6 に答える 6

26

ここで重要なのは、3つのリスト実装での挿入/削除操作の複雑さです。ArrayListには、任意のインデックスに対してO（n）の挿入/削除時間がありますが、操作がリストの最後にある場合はO（1）です。ArrayListには、任意の場所へのO（1）アクセスの便利さもあります。LinkedListも同様にO（n）ですが、リストのいずれかの端（開始と終了）での操作の場合はO（1）であり、任意の位置の場合はO（n）アクセスです。TreeListには、任意の位置でのすべての操作に対してO（logn）の複雑さがあります。

これは、任意の位置での挿入/削除に関する限り、TreeListが十分に大きいリストに対してより高速であることを明確に示しています。しかし、AFAIK、TreeListsはバイナリ検索ツリーとして実装されており、配列の単なるラッパーであるArrayListsを使用した同様の操作よりも、O（logn）操作に関連付けられた定数がはるかに大きくなっています。これにより、TreeListは小さなリストでは実際に遅くなります。また、要素をリストに追加するだけの場合、ArrayList / LinkedListのO（1）パフォーマンスは明らかに高速です。さらに、多くの場合、挿入/削除の数はアクセスの数よりもはるかに少ないため、多くの場合、ArrayListが全体的に高速になる傾向があります。リストのいずれかの端でのLinkedListの定数時間の挿入/削除により、キュー、スタック、およびDequesなどのデータ構造の実装がはるかに高速になります。

結局のところ、それはすべて、リストが正確に何のために必要かによって異なります。万能の解決策はありません。自分の仕事に最も適した実装を選択する必要があります。

于 2009-11-11T05:40:53.417 に答える
3

これは、これらのコレクションの背後にあるデータ構造によるものです。TreeListはツリーであり、比較的高速な読み取り、挿入、削除が可能です（すべてO（log n））。ArrayListは配列を使用してデータを格納するため、挿入または削除するときは、配列内のすべての項目を上下にシフトする必要があります（O（n）最悪の場合）。配列のサイズも固定されているため、現在の配列の容量を超えた場合は、新しい、より大きな配列（通常、サイズ変更を最小限に抑えるために最後の配列の2倍のサイズ）を作成する必要があります。LinkedList使用...リンクリスト。リンクリストには通常、リストの最初の（場合によっては最後の）要素への参照があります。次に、リスト内の各要素は、リスト内の次の要素（単一リンクリストの場合）または次と前の要素（二重リンクリストの場合）のいずれかへの参照を持ちます。このため、特定の要素にアクセスするには、そこに到達する前にすべての要素を反復処理する必要があります（O（n）最悪の場合）。特定の要素を挿入または削除するときは、それらを挿入または削除する位置を見つける必要があります。これには時間がかかります（O（n）最悪の場合）。ただし、最初または最後に別の要素を追加するだけのコストはほとんどありません（O（1））。

データ構造について書かれた本が全部ありますが、それらをいつ使用するかについては、より基本的なものを読むことをお勧めします。

于 2009-11-11T05:27:01.403 に答える
2

リンクリストは、リスト内の任意の場所に移動するためにノードごとにナビゲートする必要があるため（実装によっては前面と背面を保存する）、数値が非常に高いことは理にかなっています。

大きなLinkedListでの追加/挿入/削除の場合、正しい場所に到達するためにノードからノードへと多くのホッピングが必要になります。

彼らが適切なサイズのArrayListを作成して、成長する苦痛から始めるのであれば、何もありません。ArrayListが小さい場合、増大する問題は問題ではありません。

LinkedListの場合、操作がすべてリストの先頭近くにある場合は、最後にある場合よりも影響がはるかに少なくなります。

あなたがすべきことは、常にインターフェースを使用することです。例：変数とパラメーターを宣言するときにリストを作成すると、「new LinkedList（）;」を変更できます。「newArrayList（）;」へ コードのプロファイルを作成して、特定のコードでどのように機能するかを確認します。

ノードからノードにホップする必要がない速度のため、私は常にLinkedListではなくArrayListをデフォルトにします。

ツリーリストは、（コードを見なくても）両方よりも大幅に高速になると思います。木は速くなるように設計されています。

于 2009-11-11T05:27:08.907 に答える
2

ここで答えた一人一人が正しいです。それらはすべて、使用パターンに大きく依存するという概念に基づいています。つまり、万能のリストはありません。しかし、私の執筆の時点で、彼らはすべて、LinkedListが最高の場合のユースケース（イテレーターに配置された挿入）について言及するのを忘れていました（それ、または私はずさんな読者です）。つまり、あなたがしているだけではない場合

LinkedList::add(int index, E element) 
          Inserts the specified element at the specified position in this list.

これは彼らが統計を取得するために使用した方法のようですが、

iterator.insert(E element)

iteratorいずれかを介して取得

public abstract ListIterator<E> listIterator(int index)
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.

また

public Iterator<E> iterator()
Returns an iterator over the elements in this list (in proper sequence).

、その後、これまでで最高の任意の挿入パフォーマンスを得ることができます。これはもちろん、iterator（）とlistIterator（）の呼び出し回数、およびリスト内でのイテレーターの移動回数を制限できることを意味します（たとえば、リストを1回だけシーケンシャルパスして、必要なすべての挿入を実行できます）。 ）。これにより、ユースケースの数は非常に限られていますが、それでも非常に頻繁に発生するユースケースです。そして、LinkedListのパフォーマンスが、Javaだけでなく、すべての言語のすべてのコンテナーコレクションに保持されている（そして将来的にはそうなる）理由です。

PS。もちろん、上記のすべては、get（）、remove（）などの他のすべての操作に適用されます。つまり、イテレータを介した慎重に設計されたアクセスにより、実際の定数が非常に小さいすべての操作がO（1）になります。もちろん、他のすべてのリストについても同じことが言えます。つまり、イテレータアクセスを使用すると、すべてのリストが高速化されます（ただし、わずかになります）。しかし、ArrayListのinsert（）とremove（）ではありません-それらはまだO（n）になります...そしてTreeListのinsert（）とremove（）ではありません-ツリーバランシングのオーバーヘッドは避けられないものです...そしてTreeListおそらくより多くのメモリオーバーヘッドがあります...あなたは私の考えを理解します。要約すると、LinkedListは、リストに対する小さな高性能スキャンのような操作用です。それが必要なユースケースであるかどうかは、あなただけが判断できます。

PSS。そうは言っても、私も残っています

彼らはArrayListの増大する苦痛を償却または無視し、すでに配置されているLinkedList内のアイテムの挿入時間と削除時間を考慮していないと結論付けようとしました。

于 2009-11-11T06:51:31.300 に答える
1

コードが両方に対して一定時間であるメソッドのみを呼び出す場合でも、ArrayListは一般にLinkedListよりも高速であることに注意してください。たとえば、ArrayList.add（）は、単一の変数を単純化して、サイズ変更が不要な場合にカウンターをインクリメントしますが、LinkedList.add（）は、ノードを作成して複数のポインターを設定する必要もあります。さらに、LinkedListノードはより多くのメモリを必要とするため、アプリケーションの速度が低下し、ガベージコレクションはノードを処理する必要があります。

リストのいずれかの端から要素を追加または削除する必要があるが、ランダムアクセスを必要としない場合、 Java 6が必要ですが、 ArrayDequeはLinkedListよりも高速です。

LinkedListは、リスト全体を反復処理してから、途中で要素を追加または削除するのに意味がありますが、これは異常な状況です。

于 2009-11-18T07:38:44.690 に答える
1

ArrayListの場合、実行頻度が低いため、基本的にそのコストを無視できます。それが実際に問題である場合は、最初に配列を大きくしてください。

私が小さなリストを持っている場合、その時点での利点は最小限であるため、LinkedListを使用するのが理にかなっています。リストが長くなる場合は、明らかにTreeListの方が理にかなっています。

リストへのランダムアクセスを大量に行う場合は、ArrayListの方が理にかなっています。

どのコンテナを使用するかは、実際に何をするかによって異なります。それぞれに長所と短所があるため、正しいコンテナは1つではありません。経験を積むと、どのコンテナをいつ使用するかを理解できるようになります。

于 2009-11-11T05:32:12.327 に答える