32

条件を満たした場合にいくつかのオブジェクトを削除する必要があり、ArrayListどの方法がより効率的か疑問に思っています。

状況は次のとおりArrayListです。他のオブジェクトを含むクラスがあります。これを繰り返してArrayList、特定の条件を満たすすべての要素を削除する必要があります。私の知る限り、これらは削除する私のオプションです：

  1. 新規作成しArrayList、条件を満たさない要素を追加してください。繰り返しの後、古い配列リストから要素のない新しい配列リストに交換します。

  2. 新規作成しArrayList、条件を満たす要素を追加します。繰り返しの後、削除するオブジェクトで をremoveAll()渡すメソッドを使用します。ArrayList

からオブジェクトを削除するより効率的な方法はありArrayListますか?

4

13 に答える 13

46

逆方向に反復して、ArrayList を通過するときに削除することができます。これには、後続の要素をシフトする必要がないという利点があり、先に進むよりもプログラムが簡単です。

于 2009-08-21T07:52:10.760 に答える
16

別の方法: Iterator には、ArrayList に実装されているオプションの remove() メソッドがあります。繰り返しながら使用できます。

ただし、どのバリアントが最もパフォーマンスが高いかはわかりません。測定する必要があります。

starblue は、複雑さは良くないとコメントしました。それは本当です (removeAll() についても)。なぜなら、途中で要素が追加または削除された場合、ArrayList はすべての要素をコピーする必要があるためです。その場合、LinkedList の方が適切に機能するはずです。しかし、実際のユースケースを誰も知らないため、最善の解決策を選択するには、すべてのバリアントを測定するのが最善です。

于 2009-08-21T07:43:47.190 に答える
12

ほとんどのパフォーマンスは、listIteratorメソッドを使用して逆の反復を行うと思います。

for (ListIterator<E> iter = list.listIterator(list.size()); iter.hasPrevious();){
    if (weWantToDelete(iter.previous()))  iter.remove();
}

編集:ずっと後に、ラムダまたはメソッド参照を使用してリスト (または任意のコレクション!) から要素を削除する Java 8 の方法を追加することもできます。filter必要に応じて、コレクションのインプレース:

list.removeIf(e -> e.isBad() && e.shouldGoAway());

これはおそらく、コレクションをクリーンアップするための最良の方法です。内部反復を使用するため、コレクションの実装はショートカットを使用して可能な限り高速にすることができます ( ArrayLists の場合、必要なコピーの量を最小限に抑えることができます)。

于 2009-08-21T07:59:43.570 に答える
5

明らかに、言及した2つの方法のうち、リストを1回だけ通過する必要があるため、番号1の方がより効率的ですが、方法番号2では、リストを2回トラバースする必要があります（最初に削除する要素を見つけ、それらをそれらを削除します)。

実際、別のリストから要素のリストを削除することは、O(n) よりも悪いアルゴリズムである可能性が高いため、方法 2 はさらに悪いです。

イテレータ メソッド:

List data = ...;

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if (!(...)) {
        i.remove();
    }
}
于 2009-08-21T07:55:09.337 に答える
4

まず、これが本当にパフォーマンスのボトルネックであることを確認します。それ以外の場合は、最もクリーンで表現力豊かなソリューションを使用します。

それがパフォーマンスのボトルネックである場合は、さまざまな戦略を試して、何が最も速いかを確認してください。私の賭けは、新しい ArrayList を作成し、その中に目的のオブジェクトを配置して、古い ArrayList を破棄することです。

于 2009-08-21T07:53:54.440 に答える
1 
int sizepuede= listaoptionVO.size();
for (int i = 0; i < sizepuede; i++) {
    if(listaoptionVO.get(i).getDescripcionRuc()==null){
        listaoptionVO.remove(listaoptionVO.get(i));
        i--;
        sizepuede--;
     }
}

編集：インデントを追加

于 2011-05-20T16:25:46.497 に答える
1

ArrayList から要素を削除するには、隠れたコストがあります。要素を削除するたびに、要素を移動して「穴」を埋める必要があります。平均して、これはN / 2N 個の要素を持つリストの代入を必要とします。

したがって、N 要素の ArrayList から M 要素を削除するのはO(M * N)平均的です。O(N) ソリューションには、新しいリストの作成が含まれます。例えば。

List data = ...;
List newData = new ArrayList(data.size()); 

for (Iterator i = data.iterator(); i.hasNext(); ) {
    Object element = i.next();

    if ((...)) {
        newData.add(element);
    }
}

removeN が大きい場合、このアプローチは、M の値が 3 または 4 と小さい場合のアプローチよりも高速になると思います。

ただし、展開時にバッキング配列がコピーされないようnewListに、すべての要素を保持するのに十分な大きさを作成することが重要です。list

于 2009-08-21T10:16:06.663 に答える
1

あなたが直面している問題が実際にボトルネックであると確信していない限り、私は読みやすいものを選びます

public ArrayList filterThings() {

    ArrayList pileOfThings;
    ArrayList filteredPileOfThings = new ArrayList();

    for (Thing thingy : pileOfThings) {
        if (thingy.property != 1) {
            filteredPileOfThings.add(thingy);
        }            
    }
    return filteredPileOfThings;
}
于 2009-08-21T08:22:03.900 に答える
0

イテレータを使用すると、指定されたインデックスではなく、順序付けられる要素を常に処理できます。ですから、上記の件で悩む必要はありません。

Iterator itr = list.iterator();
String strElement = "";
while(itr.hasNext()){

  strElement = (String)itr.next();
  if(strElement.equals("2"))
  {
    itr.remove();
  }
于 2012-07-11T09:30:24.853 に答える
0

私は別のより速い解決策を見つけました：

  int j = 0;
  for (Iterator i = list.listIterator(); i.hasNext(); ) {
    j++;

    if (campo.getNome().equals(key)) {
       i.remove();
       i = list.listIterator(j);
    }
  }
于 2009-09-22T16:07:57.183 に答える
0

もしかしてIteratorのremove()メソッド？JDK のデフォルト コレクション クラスは、このメソッドをサポートするすべてのクリエータ イテレータである必要があります。

于 2009-08-21T07:48:56.570 に答える
0

これは直感に反していますが、これは私がこの操作を大幅に高速化した方法です。

まさに私がやっていたこと:

ArrayList < HashMap < String , String >> results; // This has been filled with a whole bunch of results

ArrayList < HashMap < 文字列 , 文字列 > > 破棄 = findResultsToDiscard(results);

results.removeall(破棄);

ただし、remove all メソッドは、2000 の配列 (ish) から約 800 の結果を削除するのに 6 秒以上 (破棄結果を取得するメソッドを含まない) を要していました。

この投稿で gustafc などによって提案された反復子メソッドを試しました。

これにより、操作がわずかに (約 4 秒まで) 高速化されましたが、それでも十分ではありませんでした。危険なことをやってみた…

 ArrayList < HashMap < String, String>> results;

  List < Integer > noIndex = getTheDiscardedIndexs(results);

for (int j = noIndex.size()-1; j >= 0; j-- ){
    results.remove(noIndex.get(j).intValue());
}

一方、getTheDiscardedIndexs は、HashMap の配列ではなく、インデックスの配列を保存します。これにより、オブジェクトの削除がはるかに高速になり (現在は約 0.1 秒)、削除する結果の大きな配列を作成する必要がないため、メモリ効率が向上します。

これが誰かに役立つことを願っています。

于 2012-08-03T16:17:05.850 に答える
-2

私はMnementhの推薦に満足しています。
ただし、注意点が1つだけあります。

 ConcurrentModificationException

複数のスレッドを実行していないことに注意してください。この例外は、複数のスレッドが実行され、スレッドが十分に同期されていない場合に発生する可能性があります。

于 2009-08-21T09:13:27.290 に答える