Laden...
FAQ

[FAQ] Listenelemente suchen und entfernen

Erstellt von ErfinderDesRades vor 13 Jahren Letzter Beitrag vor 13 Jahren 28.666 Views
ErfinderDesRades Themenstarter:in
5.299 Beiträge seit 2008
vor 13 Jahren
[FAQ] Listenelemente suchen und entfernen

Gelegentlich muß man aus einer Auflistung bestimmte Elemente entfernen. Dabei läuft man leicht in einen typischen Anfänger-Fehler, nämlich in einem Vorwärts-Durchgang die Treffer entfernen zu wollen.
Das ist in etwa vergleichbar mit dem Absägen des Astes, auf dem man sitzt. 😉

Als Beispiel nehme ich eine List<int>numbs mit Zufallszahlen, und alle Vielfachen von 3 sollen entfernt werden.

Wie es nicht geht

Die erste Variante des Fehlers würde foreach verwenden:


foreach(int n in numbs) if(n % 3 == 0) numbs.Remove(n);

Das quittiert die Laufzeit mit einer InvalidOperationException: > Fehlermeldung:

"Auflistungen können während der Enumeration nicht verändert werden" . Grund ist, dass foreach über das IEnumerable-Interface den Enumerator der Auflistung abruft, ein Objekt, welches von einem Element zum nächsten vorrückt. Wenn nun während des Enumerierens Elemente zugefügt oder entfernt werden, ist das Verhalten des Enumerators nicht definiert, und daher wird sicherheitshalber die Exception geworfen.
Die Exception ist uns übrigens sehr nützlich, denn falls der Enumerator mit einer variablen Auflistung umgehen könnte, würde er dasselbe tückische Fehlverhalten produzieren, wie die folgende Variante des Fehlers, die Vorwärts-for-Schleife:


for(int i = 0; i < numbs.Count; i++) if(numbs[i] % 3 == 0) numbs.RemoveAt(i);

Dieses würde zwar abgearbeitet werden, jedoch falsche Ergebnisse zeitigen - sehen wir die Datenmenge nach verschiedenen Durchläufen an:

[FONT]i: 0 1 2 3 4 5 6 7
n: 8 6 3 5 8 1 2 9[/FONT]

Erster Treffer bei i == 1. Danach sehen die Daten so aus:

[FONT]i: 0 1 2 3 4 5 6 7
n: 8 3 5 8 1 2 9[/FONT]

Anschließend wird i auf 2 gesetzt. Durch die Entfernung des vorigen Treffers sind aber die folgenden Elemente nach vorn gerückt, und nun liegt eine 3 auf Position 1, wird aber nicht mehr geprüft, denn Zähler i steht schon auf 2.
Das tückische daran ist, dass die übersprungene Prüfung nur dann falsche Daten erzeugt, wenn zwei Treffer aufeinander folgen.

Wie es geht

Aus obiger Betrachtung ergibt sich direkt die "naive" Lösung, nämlich die Liste eben rückwärts zu durchlaufen:


for(int i = numbs.Count; i-- > 0; ) if(numbs[i] % 3 == 0) numbs.RemoveAt(i);

(Es ist also möglich, den Ast abzusägen, man darf nur nicht zwischen sich selbst und dem Stamm sägen 😉 )

Aufwandsklasse der naiven Lösung

In üblichen arraybasierten Auflistungen (zB List<T>) werden beim Löschen eines Elementes intern alle Folge-Elemente um einen Platz nach vorne kopiert. Das heißt, bei jeder Löschung wird im Durchschnitt intern die halbe Liste durchlaufen. Eine Verdopplung der Element-Anzahl würde sowohl eine doppelte Treffer-Zahl mitbringen, als auch bei jedem Treffer doppelt so viele zu verrückende Elemente. Daraus ergibt sich eine quadratische Proportionalität zw. Anzahl der Elemente und dem Aufwand der Operation, also eine Aufwandsklasse von O(n^2).
Codestellen mit quadratischem Aufwand sollte man möglichst vermeiden, daher stelle ich im folgenden 3 Verbesserungen vor, die die unerwünschten Elemente in nur einem Durchgang entfernen (linearer Aufwand: O(n)).
Die Verbesserungen sind aber nicht bei allen Auflistungen anwendbar (Beispiele folgen), sodaß manchmal zur naiven Lösung keine Alternative besteht.

Verbesserung#1: Liste umkopieren, dabei Treffer auslassen


var list2 = new List<int>();
foreach(int n in numbs) if(n % 3 != 0) list2.Add(n);

Hierbei wird zeitweilig der doppelte Speicherplatz belegt, aber wenn das nur kurz ist, ist das nicht von Belang. Ernster ist die Gefahr, dass anderweitig noch eine Referenz auf die Ursprungs-Liste vorhanden sein mag, sodaß 1.der Speicher der Ursprungs-Liste nicht freigegeben wird 1.andernorts evtl. noch mit der veralteten Liste gearbeitet wird (Redundanz-Problem)

Verbesserung#2: Liste in sich selbst umkopieren


for(int i = 0; i < numbs.Count; i++) {
   if(numbs[i] % 3 == 0) {
      /*Die Treffer werden nicht entfernt, sondern ab dem ersten Treffer werden die folgenden 
       * Elemente nach vorn kopiert - Treffer werden dadurch überschrieben */
      int i2 = i;
      for(i++; i < numbs.Count; i++) {
         if(numbs[i] % 3 != 0) numbs[i2++] = numbs[i];
      }
      //erst ganz zuletzt werden die überzähligen Stellen vom Ende her entfernt
      numbs.RemoveRange(i2, i - i2);
   }
}

Verbesserung#3: die dafür vorgesehene Methode nutzen 😉

Der gesamte bisherige Code ist nicht praxis-relevant, und muß gewissermaßen als PseudoCode angesehen werden, denn die Auflistung List<T> bringt bereits eine Methode .RemoveAll(Predicate<T> match) mit, die genau das ausführt, was als Verbesserung#2 ausprogrammiert ist. Man muß nur einen Delegaten angeben, der bestimmt, ob ein Element zu entfernen ist, und List<T>.RemoveAll() entfernt alle diese Elemente, in nur einem Durchgang:


numbs.RemoveAll(delegate(int n) { return n % 3 == 0; });
//oder
numbs.RemoveAll(n => n % 3 == 0);

Spezielle Auflistungen

ControlCollection
Hier sind obige Verbesserungen nicht anwendbar. Da der Indexer readonly ist, kann dem i-ten Element kein anderes Control zugewiesen werden. Und natürlich kann man auch nicht eine ControlCollection durch eine andere austauschen, wie in Verbesserung#1 gezeigt. Wir müssen also auf die einfachste Lösung, das Rückwärts-Laufen, zurückgreifen.


ControlCollection ctrls = grpMultiControls.Controls;
for(int i = ctrls.Count; i-- > 0; ) if(ctrls[i] is Label) ctrls.RemoveAt(i);

Verbesserungen an der Schleife wären hier ohnehin kaum sinnvoll, da erstens die gezeigten Verbesserungen erst bei tausenden von Elementen meßbare Wirkung entfalten, und zweitens das Entfernen eines einzigen Controls und Freigabe seiner Ressourcen ungleich langsamer ist als hunderte von Schleifendurchläufen.
Im Gegenteil - man kann sogar auf Kosten der Schleifen-Performance die Lesbarkeit etwas verbessern:


foreach(int c in grpMultiControls.Controls.OfType<Label>().ToArray()) c.Dispose();

Dieser Code ähnelt sehr dem Anfänger-Fehler mit foreach, allerdings wird hier mittels .ToArray() flugs eine Kopie der Auflistung geschaffen und durchlaufen, während die Löschungen die Ursprungs-Liste treffen.

TreenodeCollection und ListviewItemCollection
Möglicherweise sind dieses die Auflistungen, aus denen am häufigsten unerwünschte Elemente gelöscht werden sollen. Wie die ControlCollection sind auch diese eng an eine andere Klasse gekoppelt, und weder als ganzes austauschbar, noch lassen sich Elemente umkopieren. Als Algorithmus kommt also ebenfalls nur die Rückwärts-Schleife in Frage.

Da die drei letztgenannten Auflistungen direkt auf dem Bildschirm angezeigt werden, ist hier bei Mehrfach-Operationen eine Optimierung der Anzeige dringend angeraten - nämlich das zeitweilige Aussetzen ihrer Aktualisierung.
Für die ControlCollection bedeutet das, eingangs ParentControl.SuspendLayout() aufzurufen, und nach Abschluß der Mehrfach-Operation ParentControl.ResumeLayout().


grpMultiControls.SuspendLayout();
grpMultiControls.Controls.OfType<Label>().ToList().ForEach(c => c.Dispose());
grpMultiControls.ResumeLayout();

Treeview und Listview dagegen warten mit den Methoden .BeginUpdate() / .EndUpdate() auf, die entsprechend zu verwenden sind.

EDIT von herbivore: Wenn es um das Löschen doppelter Elemente geht, siehe doppelte Werte einer Liste löschen.

Der frühe Apfel fängt den Wurm.