4

私は、オブジェクトの小さなリストをオブジェクトの大きなセットのサブリストとして格納するアルゴリズムに取り組んでいます。オブジェクトは本質的に順序付けられているため、順序付けされたリストが必要です。

実行される最も一般的な操作は、頻度の順になります。

  1. リストからn番目の要素を取得する（任意のnの場合）
  2. リストの最初または最後にシングルを挿入する
  3. リストから最初または最後のn個の要素を削除する（任意のn個の場合）

真ん中からの取り外しと挿入は決して行われないので、その効率を考慮する必要はありません。

私の質問は、Javaのこのユースケース（つまり、LinkedList、ArrayList、Vectorなど）に対してListのどの実装が最も効率的かということです。情報に基づいた決定を下せるように、さまざまなデータ構造の実装について説明して、回答を守ってください。

ありがとう。

ノート

いいえ、これは宿題の問題ではありません。いいえ、私にはその仕事をしてくれる軍の研究助手がいません。

4

6 に答える 6

5

最初の基準（任意のアクセス）に基づいて、ArrayListを使用する必要があります。ArrayLists（および一般的な配列）は、一定時間でルックアップ/取得を提供します。対照的に、LinkedList内のアイテムを検索するには線形の時間がかかります。

ArrayListsの場合、最後の挿入または削除は無料です。LinkedListsを使用する場合もありますが、これは実装固有の最適化になります（それ以外の場合は線形です）。

ArrayListsの場合、フロントでの挿入または削除には線形時間が必要です（スペースの一貫した再利用により、これらは実装によっては一定になる場合があります）。リストの先頭にあるLinkedList操作は一定です。

最後の2つの使用例は、互いにある程度バランスが取れていますが、最も一般的な場合は、アレイベースのストレージを確実に示唆しています。

基本的な実装の詳細に関しては、ArrayListsは基本的にメモリの単なるシーケンシャルセクションです。始まりがどこにあるかがわかっている場合は、1つの追加を実行するだけで、任意の要素の場所を見つけることができます。スペースを空けるために要素をシフトする必要があるかもしれないので、フロントでの操作は高価です。

LinkedListsはメモリ内で互いに素であり、（最初のノードを参照して）相互にリンクされたノードで構成されます。n番目のノードを見つけるには、最初のノードから開始し、目的のノードに到達するまでリンクをたどる必要があります。フロントでの操作には、ノードを作成して開始ポインターを更新するだけです。

于 2012-07-18T18:32:50.573 に答える
3

二重リンクリストに投票します。http://docs.oracle.com/javase/6/docs/api/java/util/Deque.html

于 2012-07-18T18:25:01.137 に答える
1

おそらく、この目的に最適なデータ構造は、動的配列で実装された両端キューArrayListです。これは、基本的に、内部配列の先頭ではなく中央に要素を追加し始めるものです。残念ながら、JavaArrayDequeはn番目の要素の検索をサポートしていません。

ただし、1つを自分で実装する（または既存の実装を検索する）のは非常に簡単であり、説明されている3つの操作すべてをO（1）で実行できます。

于 2012-07-26T22:36:51.797 に答える
0

間違いなくLinkedListに行きます。リストの最初/最後に値を挿入する場合と、リストの最初/最後の要素を削除する場合の両方で、O（1）で実行されます。これは、これらの操作を実行するために変更する必要があるのは、最小限のコストの操作である2つのポインターだけであるためです。

ArrayListsはO（1）のn番目の要素を取得し、LinkedListsはO（n）のn番目の要素を取得しますが、ArrayListsは、要素が挿入されるときにサイズを調整しなければならないという危険を冒します。ArrayListに割り当てられたメモリが使い果たされ、別の要素を挿入しようとするとどうなると思いますか？何が起こるかというと、ArrayListはそれ自体を複製してから、より多くのメモリを割り当てます（最初に割り当てた量の2倍になります）。これは非常にコストのかかる操作です。LinkedListsにはこの問題はありません。これも、ポインタを追加するだけだからです。

Javaベクトルについてはよくわかりませんが、C ++ベクトルのようなものであれば、ArrayListsと非常によく似ています。

これがお役に立てば幸いです。

于 2012-07-18T18:38:31.887 に答える
0

効率を気にしないのであれば、混乱を最小限に抑えながら、arrayListを使用してこれらすべてを実行できます。

フロントまたはエンドにのみ挿入する場合は、ある種のキューまたはスタックを使用します。オーバーヘッドが最小です。または、リンクリストを使用することもできます。

リンクリストを使用して最初または最後からN個の要素を削除するには、1つのノードと、その前または後のノードを削除するだけです。つまり、最初の5つの要素を削除した場合は、5番目の要素とそれが消える前の要素を削除するだけです。また、最後の6つの要素を削除すると、最後から6番目の要素を削除すると、残りは消えます。そして、Javaがガベージコレクションを行います。これは、この操作では（1）の順序になります。

これは宿題の質問ですか？

于 2012-07-18T18:25:29.313 に答える
0

Long to Objectのjava.util.TreeMap、およびi + tm.firstKey（）のインデックスを使用

于 2016-08-21T15:13:03.940 に答える