6

長いリストを安価に追加できるJavaのリストデータ構造を探しています。LinkedList を試してみましたが、addAllのドキュメントで、2 つのリストを追加するためにイテレータが使用されていることがわかりました。これは、追加されるリストが操作中に複製されることを意味します。イテレータは、すべての単一要素を返すリスト全体をウォークスルーします。2 つのリストを追加する際に反復を省略できるコレクションはありますか?

4

10 に答える 10

6

Guava の Iterables.concatメソッドを使用して、連結された Iterable View を作成できます。

Iterable<T> combined = Iterables.concat(list1, list2);
  • これは、あるリストから別のリストに要素をコピーしません..
  • したがって、リストは変更されません..
  • また、これは新しいリストを作成しませんIterable(リストではない を作成します)

基本的にIterable、リストを連続して反復できる を作成しtwoます (list1 の要素を反復し、次に list2 の要素を反復します..

注: - の連結としてリストが必要な場合、これはあまり役に立たない可能性があります..リストは作成されませんが、Iterable が作成されるためです..その場合、リストtwo listsを作成する以外に選択肢はありませんIteratingそしてcopyあなたのそれぞれの参照..

ドキュメントから： -

2 つの iterable を 1 つの iterable に結合します。返された iterable には、a の要素をトラバースし、その後に b の要素をトラバースするイテレータがあります。ソース反復子は、必要になるまでポーリングされません。返された iterable のイテレータは、対応する入力イテレータが remove() をサポートしている場合、remove() をサポートします。

このメソッドのvar-argsバージョンもあります。Docs を参照してください。これは、任意の数のリストを取得でき、それらのリストを順番に反復処理できる Iterables を返します。したがって、次のようにすることができます。

Iterable<T> combined = Iterables.concat(list1, list2, list3, list4, ...);

このリンク --> google-guava-libraries-essentialsも興味があるかもしれません..

于 2012-10-10T12:07:08.540 に答える
5

すべての「追加」操作は、基礎となるコレクションについて何の仮定もしていないためです。技術的には、2 つのリンクされたリストを直接追加できますが、追加は一般的でなければならないため、反復が使用されます。

直接連結を許可しないもう 1 つの正当な理由は、追加後に 1 つのリストを変更すると他のリストにも影響するという事実です。これは望ましいプロパティではないと確信しています。

于 2012-10-10T12:02:44.670 に答える
4

ArrayList のaddAllはそれを配列に変換し、システム コールを使用してコピーします ( System.arraycopy )。これはネイティブであるため、Java でループするよりも高速である必要があります。安価なアペンダーはないと思います。

于 2012-10-10T12:03:13.113 に答える
3

反復しないため、ArrayListのaddAllの方が高速である可能性がありますが、System.arrayCopyを使用します。コードは次のようになります。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
        int numNew = a.length;
    ensureCapacity(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
    return numNew != 0;
    }
于 2012-10-10T12:05:16.747 に答える
1

これは、追加されるリストが操作中に複製されることを意味します。

イテレータを作成しても、コレクションは複製されません。

ほとんどの場合、addAll メソッドは toArray() を呼び出して、コレクションの要素を配列として複製するアトミックにデータが抽出されるようにします。これは、Iterator を使用して行う可能性があります。

2 つのリストを追加する際に反復を省略できるコレクションはありますか?

いいえ。ただし、これが本当に重要な場合は、自分でコレクションを反復できます。

最も効率的なのはおそらく

List<E> list1 = ... random access list ...
List<E> list2 = ... random access list ...

for(int i = 0; i < list2.size(); i++)
    list1.add(list2.get(i));

これはオブジェクトを作成せず、list2 のサイズのO(n)時間があります。n

于 2012-10-10T12:15:02.287 に答える
0

addAllメソッドのデフォルトの実装AbstractCollectionsはイテレータを使用して追加しますが、addAllメソッドはカスタム固有の実装を提供するサブクラスでオーバーライドされます

好き

  • ArrayListはSystem.arraycopy
  • LinkedListは、ループを使用して要素をトラバースします。
于 2012-10-10T12:05:22.803 に答える
0

with that behavior the list added to the first list will get consumed (i.e. modified) or results in the second list becoming a sublist of the bigger one with all kinds of gotchas (like what happens if you add a list twice...),

the addAll has an implicit const argument (meaning that the second list will remain unmodified over several calls), so this behavior won't exist unless you roll your own

于 2012-10-10T12:21:42.193 に答える
0

そのようなコレクションクラスを見つけたとしても、それがJavaの将来のバージョンでそのように機能し続けることを保証することはできません。これは、これがコレクションインターフェイスで指定されていない動作であり、したがってクラス開発者の気まぐれの影響を受けるためです。

もちろん、独自のコレクションクラスを作成することもできますが、それでも、他のコレクションクラスの動作について推測することになります。

于 2012-10-10T12:04:09.990 に答える
0

標準のAPIには方法がないと思いますが、ニーズに応じて、自分で実装してみてください。たとえば、addAllメソッドを呼び出すたびに追加されるコレクション参照のリストを内部に持つものを実装できます。

于 2012-10-10T12:06:55.777 に答える
0

私は単に ArrayList を取り、喜んで addAll() 私のものをそれに追加します。選択した List 実装が addAll() 操作をどのように実行するかは実際には問題ではありません。反復または toArray はどちらも比較的安価であり、これがパフォーマンスのボトルネックになる可能性はほとんどありません (アプリケーションがリスト要素を操作するだけでなく、有用な作業を行うと仮定すると)リストを作成します...)。

addAll() の反復を回避する方法は実際にはありません。N 個のソース リストの要素を含む独立したリストが必要な場合は、要素の参照をどこかにコピーする必要があります (addAll() の後でソース リストを変更することもできますが、連結リストに影響を与えてはならないため、コピーは避けられません)。

リストのセマンティクスが本当に必要ない場合(ソースに依存しない場合)、既に提案されている Guava を使用して、複数のリストのビューを作成します (または、依存関係が必要ない場合は、ロケット科学ではない独自のロールを作成します)。 .

于 2012-10-10T12:32:55.840 に答える