Laut der MSDN-Dokumentation zur List<T>.Clear -Methode :
Diese Methode ist eine O (n) Operation, wo n ist Count.
Warum O (n)? Ich frage, weil ich annehmen würde, dass das Löschen eines List<T> einfach dadurch erreicht werden könnte, dass intern ein neues T[] -Array zugewiesen wird. Keine andere Klasse könnte einen Verweis auf dieses Array haben, daher sehe ich keinen Schaden in diesem Ansatz.
Nun, vielleicht ist das eine blöde Frage ... ordnet man ein T[] Array selbst an O (n)? Aus irgendeinem Grund hätte ich das nicht gedacht; aber vielleicht ist es (ist mein Mangel an einem C.S. Grad gerade jetzt?). Wenn dem so ist, nehme ich an, das würde es erklären, denn nach der gleichen oben zitierten Dokumentation bleibt die Kapazität der Liste unverändert, was bedeutet, dass ein Array gleicher Größe konstruiert werden müsste.
(Auch dies scheint nicht die richtige Erklärung zu sein, da die Dokumentation dann hätte sagen sollen: "where n is Kapazität " - nicht Count *).
Ich vermute nur , dass diese Methode, anstatt ein neues Array zuzuordnen, alle Elemente des aktuellen zerlegt; und ich bin neugierig zu wissen, warum das so wäre.
* Hans Passant wies in einem Kommentar auf LukeHs Antwort ClearList<T> festgelegt wurden; Es muss nicht alle Elemente, die hinter diesen Elementen liegen, "nullstellen".
Soweit mir bekannt ist, ruft die aktuelle Implementierung einfach Array.Clear in seinem internen Array T[] und Array.Clear ist ein O (n) -Prozess. (Wie Hans in den Kommentaren hervorhebt, sind die MSDN-Dokumente korrekt, dass die n in diesem Fall die Liste ist Count , nicht die Capacity .)
Aber selbst wenn es intern nur ein neues T[] -Array zugewiesen hätte, wäre das immer noch ein O (n) -Prozess, weil die Zuweisung eines Arrays der Größe n die Initialisierung aller n -Elemente auf ihre Null / Null erfordert / Standardzustand.
Natürlich gibt es nichts, was eine Art interner Trickserei aufhalten könnte, bei der das Array mit der Länge 0 oder 42 oder was auch immer initialisiert und dann bei Bedarf automatisch wieder expandiert werden könnte, um die gesamten O (n) -Kosten zu amortisieren .
Weil die Implementierung von List<T>.Clear() Array.Clear() auf dem backign-Array der Liste aufruft und nach Dokumentation diese Methode setzt alle Elemente dieses Arrays auf null .
Ich vermute, dass der Grund dafür, dass das vorhandene Array gelöscht wird, anstatt dass ein neues erstellt wird, dass das .NET-Team festgestellt hat, dass es effizienter ist, ein vorhandenes Array zu löschen, anstatt ein neues zuzuweisen. Das Zuweisen eines neuen Arrays benötigt auch Zeit / Speicher, daher ist es ein Kompromiss, der für die üblichen Nutzungsszenarien zu optimieren versucht.
List<T>.Clear() ruft Array.Clear() auf, wie hier zu sehen:
Andererseits ruft Array.Clear() eine externe Funktion auf, die die Elemente des Arrays, die O (n) ist, auf null setzt:
List<T> Listen enthalten einige Objekte. Das Zuweisen eines neuen List<T> löscht die Objekte in der alten Liste nicht, daher ist es keine Operation clear .
Die Operation clear führt einen linearen einmaligen Durchlauf durch die Liste durch und löscht alle Elemente einzeln. Da n -Elemente vorhanden sind, dauert dies O(n) time.
Die Zuweisung eines T[] hängt davon ab, ob eine Größe angegeben ist. Wenn eine Größe angegeben wird, muss der Speicher für jedes Element oder zumindest für jeden Zeiger für dieses Element reserviert werden. Also würde das O(n) brauchen. Wenn wir jedoch einfach einen Zeiger für T[] initialisieren, würde das O(1) time benötigen.
P.S. CS-Grad bedeutet nicht automatisch, dass du dieses Zeug weißt (oder dich daran erinnerst) ... traurig, aber, wahr. Der Mangel an CS Grad ist überhaupt nicht schädlich.
Tags und Links .net performance list big-o clear