Elemente aus einer Liste entfernen, während sie durchlaufen werden

226051
lxcky

Ich brauchte eine Möglichkeit, Elemente zu entfernen, die sich Listwährend einer Weile durchzogen haben.

Angeblich so etwas (illegaler Code) :

List<Integer> nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
...
nums.add(10);

System.out.println("BEFORE REMOVE: " + nums);

for (Integer integer : nums) {
    if (integer < 3) {
        //not allowed
        nums.remove(integer);
    }
}

Aber wir alle wissen, dass der obige Code nicht erlaubt ist.

Was ich jetzt mache, ist, dass ich ein anderes Listerzeuge, bei dem ich jedes Element einsetze, das eine bestimmte Bedingung erfüllt, dann durchlaufen, Listum die Elemente zu erhalten, die ich zuerst entfernen muss List.

List<Integer> toRemove = new ArrayList();
for (Integer integer : nums) {
    if (integer < 3) {
        toRemove.add(integer);
    }
}

for (Integer integer : toRemove) {
    nums.remove(integer);
}

System.out.println("AFTER REMOVE: " + nums);

Ich weiß, es ist nicht wirklich lang, aber gibt es einen besseren Weg, dies zu tun?

Gibt es eine API, die ich verwenden kann?

Antworten
46
Ich denke, du kannst nums.removeAll verwenden (toRemove) Ishan Fernando vor 2 Jahren 0

5 Antworten auf die Frage

64
Simon Forsberg

Dafür gibt es mehrere Möglichkeiten. Schauen wir uns die Alternativen an:

Iteration über eine Kopie, Entfernen vom Original

Dies ist eine einfache Lösung für das zugrunde liegende Problem Ihres ersten Codes: A ConcurrentModificationExceptionwird ausgelöst, weil Sie die Liste durchlaufen und gleichzeitig daraus entfernen.

Eine einfache Lösung besteht darin, eine Kopie der Liste zu erstellen und diese zu durchlaufen.

for (Integer integer : new ArrayList<>(nums)) {
    if (integer < 3) {
        nums.remove(integer);
    }
}

Nachteile dieses Ansatzes:

  • Erstellt eine Kopie der ursprünglichen Liste, für die Speicher erforderlich ist, und eine Operation, deren Leistung vom Typ der Liste abhängt (ArrayList, LinkedList usw.).
  • Darüber hinaus nums.remove(value)ist eine Operation \ $ O (n) \ $. Machen Sie diese Schleife insgesamt \ $ O (n ^ 2) \ $

Java 8-Streams

List<Integer> filteredList = nums.stream().filter(i -> i >= 3).collect(Collectors.toList());

Nachteile:

  • Ändert die vorhandene Liste nicht wirklich. Wenn also Verweise auf die Liste auf verschiedene Variablen verteilt sind, haben Sie noch einige alte Elemente, die in dieser Liste nicht enthalten sein sollten.
  • Erstellt verschiedene Stream-bezogene Objekte, die möglicherweise nicht die effektivste Option sind.

Auf der anderen Seite gehört dies zu den schnellsten Listen mit größeren Listen.

Wenn Sie Java 8 nicht verwenden:

List<Object> originalList;
List<Object> newList = new YourFavoriteListType<>();
for (Object obj : originalList) {
    if (shouldKeep(obj)) {
        newList.add(obj);
    }
}

Iterator.remove ()

Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    Integer integer = it.next();
    if (integer < 3) {
        it.remove();
    }
}

Der einzige Nachteil dieses Ansatzes besteht darin, dass Sie Ihr for-each auf a umstellen müssen while. Dieser Ansatz ist jedoch am effizientesten, insbesondere LinkedListwenn er \ $ O (n) \ $ ist (dies ist $ O (n ^ 2) \ $, ArrayListda er bei jedem remove(index)Aufruf Array-Daten kopieren muss ). Dies ist der Ansatz, den ich in den meisten Fällen empfehlen würde.

Hinweis: Anstelle einer while-Schleife kann auch Folgendes geschrieben werden:

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    Integer integer = it.next();
    ...

Siehe auch

"Wann sollte LinkedList über ArrayList verwendet werden?" bei Stapelüberlauf

Es ist "O (n)" für eine "LinkedList", aber "O (n ** 2)" für eine "ArrayList". Der Iterator kann nichts unternehmen, um das Verschieben von Daten zu verhindern. maaartinus vor 5 Jahren 0
@maaartinus Richtig, aber es hängt ein wenig davon ab, wie `System.arraycopy` implementiert wird, da es ein` native`-Aufruf ist. Ich neige dazu, es als einen reinen Gedächtniskopieraufruf zu betrachten, den ich eher als O (1) anstelle von O (n) betrachte, aber eine [SO-Antwort] betrachte (http://stackoverflow.com/a/25494799) / 1310566) Es scheint, als wäre es O (n). Simon Forsberg vor 5 Jahren 0
Es war ein nativer Aufruf, als Java extrem langsam war. Es ist keine magische Kugel mehr. Nun, es ist eine intrinsische JVM, was bedeutet, dass JITc den Code durch etwas intelligentes und schnelles ersetzt (mithilfe von XMM-Registern). Es bleibt aber immer noch "O (n)". Ich könnte mir vorstellen, mit virtuellen Speicher-Mappings herumzuspielen, was noch viel schneller wäre, aber immer noch `O (n)`. Auf jeden Fall würde es für Verschiebungsbeträge gelten, die ein Vielfaches der Seitengröße sind. Vergessen wir es also. maaartinus vor 5 Jahren 2
@maaartinus Um O (n) für eine `ArrayList` zu behalten, schleifen Sie einfach alle zu entfernenden Elemente in einer separaten Sammlung ein, und rufen Sie` removeAll () `in der` ArrayList` auf. bowmore vor 5 Jahren 1
@bowmore Richtig, aber der Separat muss dafür Zugriff auf "O (1)" haben. Du brauchst also so etwas wie eine HashMap, die wiederum einen relativ hohen Overhead hat (nicht wirklich hoch, aber hoch im Vergleich zu einer Liste). Ich würde wetten, dass das Sammeln der * gesuchten * Elemente einer zweiten Liste mindestens 3x schneller ist. maaartinus vor 5 Jahren 0
18
Bob Davies

Wir hatten gerade etwas sehr ähnlich zu tun (also warum ich hier bin), landete mit Java8 ‚sCollection.removeIf(Predicate<? super E> filter)

Mit Ihrem Code würde es so aussehen:

nums.removeIf((Integer i)->{return i<3;});

Und wenn Sie die Entfernungen sammeln wollten:

List<Integer> removed = new ArrayList<>();
nums.removeIf(
    (Integer i)->{
        boolean remove = i<3;
        if (remove) {
            removed.add(i);
        }
        return remove;
    });
Ich mag diesen Weg für Java 8, da er viel übersichtlicher und dennoch klar genug ist. Intern jedoch (mit Blick auf den JDK-Code) scheint es immer noch einen Iterator zu verwenden und iterator.remove () aufzurufen. Daher gelten die in anderen Beiträgen aufgeführten Überlegungen zur Leistung weiterhin. kg_sYy vor 4 Jahren 3
6
maaartinus

Von den anderen vorgestellten Lösungen scheinen alle bis auf Java 8 zu sein O(n**2), dh zu langsam, wenn die Liste (*) etwas größer wird.

Die einfachste schnelle Lösung ist das Erstellen einer leeren Liste und das Hinzufügen aller Elemente mit mindestens drei Elementen.

Wenn Sie die ursprüngliche Liste ändern müssen, reinigen Sie sie danach und fügen Sie alle Elemente aus der Hilfsliste hinzu.


(*) Es sei denn, es ist ein LinkedList, was hier hervorragend ist. Aber seine Leistung in allen anderen Szenarien ist so schrecklich, dass sie praktisch nie verwendet werden sollte.

3
IEatBagels

Zusätzlich zu @ SimonAndres Antwort könnten Sie eine umgekehrte for-Schleife verwenden, um durch Ihr Array Elemente zu entfernen, die Sie nicht möchten. Aufgrund der removeMethode bleibt es eine O (n ^ 2) -Operation. Also ist dieser Ansatz nicht besser, aber es ist ein anderer Weg.

for(int index = array.size() - 1; index >= 0; index--) {
    if(array.get(index) < 3){
        array.remove(index);
    }
}
Es ist etwas schneller, da es keine Elemente bewegt, die später entfernt werden müssen. Aber einverstanden, es ist immer noch "O (n ** 2)". maaartinus vor 5 Jahren 1
`array.get` ist eine langsame Operation auf einer` LinkedList`. Besser ist es, `array.listIterator ()` zu verwenden, das rückwärts gehen kann. Simon Forsberg vor 5 Jahren 0
Die Iteration mit einer altmodischen for-Schleife löst jedoch die `ConcurrentModificationException`. (Selbst wenn es sich um einen Forward-Index handeln würde, könnten Sie den Index jedes Mal verringern, wenn ein Element entfernt wurde.) Simon Forsberg vor 5 Jahren 0
Nun, das OP hat eine Arraylist, also bin ich zur ArrayList gegangen! Und ich finde es klarer, eine umgekehrte Schleife zu verwenden, anstatt sich mit dem Index innerhalb der Schleife zu beschäftigen IEatBagels vor 5 Jahren 0
Weil das ArrayList.get eine O (1) -Operation ist IEatBagels vor 5 Jahren 0
Stimmen Sie völlig zu, dass es besser ist, eine umgekehrte Schleife zu verwenden, als sich mit dem Index zu beschäftigen! Simon Forsberg vor 5 Jahren 0
3
janos

Eine andere vielleicht interessante Option ist die Verwendung von CopyOnWriteArrayList:

@Test
public void testCanRemoveFromCopyOnWriteArrayList() {
    List<Integer> nums = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    for (Integer num : nums) {
        if (num < 3) {
            nums.remove(num);
        }
    }
    assertEquals(Arrays.asList(3, 4, 5), nums);
}

Der Nachteil ist offensichtlich aus dem Namen der Klasse: Sie kopiert die zugrunde liegende Liste vor jedem Schreibvorgang. Diese Klasse ist für Beobachterlisten konzipiert, die selten geändert und häufig durchlaufen werden. Ich bin mir nicht sicher, ob dies auf Ihren Fall zutrifft (ob das Löschen von der Liste häufig ist oder nicht), aber ich dachte, ich würde das nur für den Fall erwähnen.