Elemente aus der Liste entfernen oder eine neue Liste erstellen?

Question

Oft komme ich zu einem Punkt, wo ich eine ArrayList iterieren muss und eine Teilmenge daraus basierend auf einer Bedingung erstellen möchte.

Vom Leistungsstandpunkt: ist es besser, Iterator und iterator.remove() für die Elemente zu verwenden, die ich entfernen möchte, oder sollte ich diese Elemente zu einer neuen Liste hinzufügen?

for (Iterator<Object> it = list.iterator(); it.hasNext();) { 
    Object item = it.next(); 
    if (!conditionMatches(item)) { 
     it.remove(); 
    } 
} 

oder

List<Object> newList = new ArrayList<>(); 
for (Object item : list) { 
    it (contitionMatches(item)) { 
     newList.add(item); 
    } 
} 

Answer 1

wenn Sie Werte aus der Liste zu entfernen, müssen Sie es von Ende machen dies zu starten, wie:

for (int i=list.size()-1; i>=0; i--) { 
    if (contitionMatches(list.get(i))) { 
     list.remove(i); 
    } 
} 

Answer 2

Zeitkomplexität: Option 2 am besten

Raumkomplexität: Optio n 1 ist am besten

ArrayList remove ist O (n), während add ist O (1), Sie müssen jedoch neuen Speicher für die neue Liste zuweisen.

Answer 3

Die zweite Option ist schneller, da nicht alle nachfolgenden Elemente verschoben werden, wenn das Element an der aktuellen Position entfernt wird.

Wenn es um größere ArrayList s geht, wage ich sogar zu sagen, dass die erste Option ein Anti-Pattern ist.

Answer 4

Option 1 funktioniert nicht für schreibgeschützte Listen wie die von Arrays.asList zurückgegebenen.

Auch remove von ArrayList ist eine erhebliche Kosten, wenn die Liste ist so lang wie viel von der Backing-Array kopiert werden muss.

Option 2 funktioniert für alle Listen.

Es ist auch das Muster, das wir mit Strömen angeregt werden zu verwenden:

List<String> l = Arrays.asList("A","B","C"); 
    List<String> filtered = l.stream() 
      .filter(s -> s.equals("A")) 
      .collect(Collectors.toList()); 

IMHO - dieses verwenden. Die Einsparungen in Option 1 sind illusorisch.

Answer 5

Wenn Sie nur ein Element entfernen müssen, können Sie es auf beide Arten tun. Wenn Sie alle Elemente nach einem bestimmten Punkt entfernen möchten, können Sie dies auf beide Arten tun (zum Entfernen rückwärts durchlaufen). Im Allgemeinen wird der Kopiervorgang jedoch viel weniger Zeit benötigen. Wenn Sie die Liste an Ort und Stelle ändern möchten, können Sie removeIf in Betracht ziehen. Obwohl die Dokumentation nicht angibt, wie es funktioniert, verfolgt es höchstwahrscheinlich einen "nach" - und "aus" -Index und verschiebt alle Elemente in einem einzigen Durchgang. Ob der Kopier- oder Modifizierungsansatz am besten passt, hängt sicherlich davon ab, wie Sie die Liste verwenden, und (wenn meine Schätzung von removeIf korrekt ist) kann auch davon abhängen, welcher Anteil der Elemente entfernt wird.