5

次の宣言があります。

ArrayList<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
list.add("2");
list.add("3");
list.add("4");

ここで私の質問は次のとおりです。リストから「2」を削除したい場合、どちらの方法が良いですか?

最初の方法:

for(int i = 0; i < list.size(); i++) {
    if(list.get(i).equals("2")) {
        list.remove(i);
        i--;
    }
}

2番目の方法:

Iterator<String> iterator = list.iterator();
    while(iterator.hasNext())
        if(iterator.next().equals("2"))
            iterator.remove();

両方とも適切に保護されており、どちらがより効率的ですか?

IndexOutOfBoundsエラーを発生させずに ArrayList から要素を削除する他の方法はありますか?

4

4 に答える 4

5

実際、より速いのは

list.removeAll(Collections.singleton("2"));

舞台裏では、ArrayList@Edmund が示唆するように基本的に配列の新しいコピーを作成しますが、より低いレベルでパフォーマンスが向上する可能性があります。

それでも、他の人が述べたように、LinkedList一般に、大きなリストから複数の要素を削除する場合のパフォーマンスは向上します。

( に切り替えることにしたLinkedList場合でも、上記のコードを引き続き使用できますが、作成されたシングルトン コレクションと発生するいくつかの追加のメソッド呼び出しに対して、少しのオーバーヘッドで iterator メソッドを使用することと同じです。)

于 2012-04-16T01:44:30.960 に答える
2

どちらの方法でも、要素を削除するたびに要素を下にシフトする必要があります。リストが非常に大きい場合は、新しいリストを作成する方が高速である可能性があります。

ArrayList<String> newList = new ArrayList<String>();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String val = iterator.next();
    if(!val.equals("2"))
        newList.add(val);
}

/* Or just return newList, depending on how list is used in subsequent code. */
list.clear();
list.addAll(newList);

LinkedListの代わりに使用することを考えることができますArrayList。しかし、最も効率的な方法を見つけるには、ベンチマーク (現実的なユース ケースを使用) が最善の方法です。

于 2012-04-16T01:25:52.273 に答える
0

個々の要素については、for ループは正常に機能します(まあ、削除すると機能しますi---remove()要素が自動的に左にシフトします) (いいえ、正常に機能します)。あなたの反復方法もそうです。

の最後まで繰り返しているだけでArrayList、そこから降りることはありません。効率の面では、これは面倒です。サイズ 100,000 のランタイムをサンプルして、それがどうなるかを確認することをお勧めします。(リストがどれほど大きくても、O(N) 操作の順序のままです。)

于 2012-04-16T01:24:13.173 に答える
-1

私はいくつかのデータ構造の本でそれを読んだことがありますが、イテレータアプローチの方が優れています。

ループの下で list.remove 呼び出しの場合、0 インデックスから削除するアイテムのインデックスまでのすべての時間で開始され、要素を削除して影響を受ける要素をシフトすると、o(n2) プロセスになります。

しかし、iterator.remove の場合、要素はイテレータによってアクセスされるため、リストの先頭に戻る必要がなく、したがって o(n) プロセスが削除されます。

于 2012-04-16T01:41:02.013 に答える