Sammlungen und Datenstrukturen

Ähnliche Daten können häufig effizienter verarbeitet werden, wenn sie als Sammlung gespeichert und bearbeitet werden. Sie können die System.Array Klasse oder die Klassen in den System.Collections, System.Collections.Generic, System.Collections.Concurrentund System.Collections.Immutable Namespaces verwenden, um einzelne Elemente oder einen Bereich von Elementen in einer Auflistung hinzuzufügen, zu entfernen und zu ändern.

Es gibt zwei Haupttypen von Sammlungen; generische Auflistungen und nicht generische Auflistungen. Generische Auflistungen sind zur Kompilierungszeit typsicher. Daher bieten generische Sammlungen in der Regel eine bessere Leistung. Generische Auflistungen akzeptieren einen Typparameter, wenn sie erstellt werden. Sie müssen nicht in den Object Typ umwandeln, wenn Sie Elemente aus der Sammlung hinzufügen oder daraus entfernen. Darüber hinaus werden die meisten generischen Sammlungen in Windows Store-Apps unterstützt. Nicht generische Auflistungen speichern Elemente als Object, erfordern eine Umwandlung, und die meisten werden für die Windows Store-App-Entwicklung nicht unterstützt. Allerdings finden Sie möglicherweise in älterem Code auch nicht generische Auflistungen.

In .NET Framework 4 und höheren Versionen bieten die Auflistungen im System.Collections.Concurrent Namespace effiziente threadsichere Vorgänge für den Zugriff auf Sammlungselemente aus mehreren Threads. Die unveränderlichen Auflistungsklassen im System.Collections.Immutable Namespace (NuGet-Paket) sind inhärent threadsicher, da Vorgänge für eine Kopie der ursprünglichen Auflistung ausgeführt werden und die ursprüngliche Auflistung nicht geändert werden kann.

Allgemeine Sammlungsmerkmale

Alle Auflistungen stellen Methoden zum Hinzufügen, Entfernen oder Suchen von Elementen in der Auflistung bereit. Darüber hinaus verwenden alle Auflistungen, die die ICollection Schnittstelle oder die ICollection<T> Schnittstelle direkt oder indirekt implementieren, diese Features:

• Die Möglichkeit zum Aufzählen der Sammlung

  .NET-Auflistungen implementieren entweder System.Collections.IEnumerable oder System.Collections.Generic.IEnumerable<T>, um das Durchlaufen der Auflistung zu ermöglichen. Ein Enumerator kann als beweglicher Zeiger auf jedes Element in der Sammlung betrachtet werden. Die Anweisungen foreach, in und For Each...Next verwenden den Enumerator, der mit der GetEnumerator-Methode verfügbar gemacht wird, und verbergen die Komplexität der Bearbeitung des Enumerators. Darüber hinaus gilt jede Auflistung, die System.Collections.Generic.IEnumerable<T> implementiert, als ein Typ, der abgefragt werden kann, und kann mit LINQ abgefragt werden. LINQ-Abfragen stellen ein gängiges Muster für den Zugriff auf Daten bereit. Sie sind in der Regel präziser und lesbarer als Standardschleifen foreach und bieten Filter-, Sortier- und Gruppierungsfunktionen. LINQ-Abfragen können auch die Leistung verbessern. Weitere Informationen finden Sie unter LINQ to Objects (C#),LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Introduction to LINQ Queries (C#) und Basic Query Operations (Visual Basic).

• Die Möglichkeit, den Sammlungsinhalt in ein Array zu kopieren

  Alle Auflistungen können mithilfe der CopyTo Methode in ein Array kopiert werden. Die Reihenfolge der Elemente im neuen Array basiert jedoch auf der Reihenfolge, in der der Enumerator sie zurückgibt. Das resultierende Array ist immer eindimensional mit einer unteren Grenze von Null.

Viele Auflistungsklassen enthalten außerdem die folgenden Funktionen:

• Eigenschaften "Kapazität" und "Anzahl"

  Die Kapazität einer Auflistung ist die Anzahl der Elemente, die sie enthalten kann. Die Anzahl der Elemente einer Sammlung ist die Gesamtzahl der Elemente, die sie tatsächlich enthält. Einige Sammlungen verbergen die Kapazität oder die Anzahl oder beides.

  Die meisten Sammlungen erweitern die Kapazität automatisch, wenn die aktuelle Kapazität erreicht ist. Der Speicher wird neu zugeordnet, und die Elemente werden aus der alten Sammlung in die neue kopiert. Dieser Entwurf reduziert den Code, der für die Verwendung der Auflistung erforderlich ist. Die Leistung der Sammlung kann jedoch negativ beeinflusst werden. Zum Beispiel, für List<T>, wenn Count kleiner als Capacity ist, ist das Hinzufügen eines Elements ein O(1)-Vorgang. Wenn die Kapazität erhöht werden muss, um das neue Element aufzunehmen, wird das Hinzufügen eines Elements zu einem O(n)-Vorgang, wobei nCount ist. Die beste Methode, um eine schlechte Leistung zu vermeiden, die durch mehrere Reallocations verursacht wird, besteht darin, die anfängliche Kapazität auf die geschätzte Größe der Sammlung festzulegen.

  Ein BitArray ist ein Sonderfall; seine Kapazität entspricht seiner Länge, die wiederum seiner Anzahl entspricht.

• Eine konsistente untere Grenze

  Die untere Grenze einer Auflistung ist der Index des ersten Elements. Alle indizierten Auflistungen in den System.Collections-Namespaces haben eine untere Grenze von 0 (Null), d. h. sie sind 0-indiziert. Array weist standardmäßig eine untere Grenze von Null auf. Eine andere untere Grenze kann jedoch bei der Erstellung einer Instanz der Array-Klasse mit Array.CreateInstance definiert werden.

• Synchronisierung für den Zugriff von mehreren Threads (System.Collections nur Klassen).

  Nicht generische Auflistungstypen im System.Collections-Namespace bieten durch die Synchronisierung ein gewisses Maß an Thread-Sicherheit; in der Regel werden sie durch die SyncRoot- und IsSynchronized-Members verfügbar gemacht. Diese Auflistungen sind standardmäßig nicht threadsicher. Wenn Sie skalierbaren und effizienten Multithreadzugriff auf eine Auflistung benötigen, verwenden Sie eine der Klassen im System.Collections.Concurrent Namespace, oder erwägen Sie die Verwendung einer unveränderlichen Auflistung. Weitere Informationen finden Sie unter Thread-Safe Sammlungen.

Auswählen einer Sammlung

Im Allgemeinen sollten Sie generische Auflistungen verwenden. In der folgenden Tabelle werden einige allgemeine Sammlungsszenarien und die Auflistungsklassen beschrieben, die Sie für diese Szenarien verwenden können. Wenn Sie mit generischen Sammlungen noch nicht vertraut sind, hilft Ihnen die folgende Tabelle bei der Auswahl der generischen Sammlung, die für Ihre Aufgabe am besten geeignet ist:

Algorithmische Komplexität von Sammlungen

Bei der Auswahl einer Sammlungsklasse lohnt es sich, potenzielle Kompromisse bei der Leistung zu berücksichtigen. Verwenden Sie die folgende Tabelle, um zu referenzieren, wie verschiedene änderbare Sammlungstypen in algorithmischer Komplexität mit ihren entsprechenden unveränderlichen Gegenstücken verglichen werden. Häufig sind unveränderliche Sammlungstypen weniger leistungsfähig, bieten aber Unveränderlichkeit, was oft einen vergleichbaren Vorteil darstellt.

Eine List<T> kann mithilfe einer for Schleife oder einer foreach Schleife effizient aufgezählt werden. Eine ImmutableList<T>-Klasse führt jedoch aufgrund der O(log for)-Zeit für ihren Indexer in einer n-Schleife zu schlechten Ergebnissen. Das Aufzählen eines ImmutableList<T> mit einer foreach-Schleife ist effizient, da ImmutableList<T> einen binären Baum zum Speichern der Daten nutzt, statt eines Arrays wie es List<T> verwendet. Ein Array kann schnell indiziert werden, während ein binärer Baum durchlaufen werden muss, bis der Knoten mit dem gewünschten Index gefunden wird.

Darüber hinaus hat SortedSet<T> die gleiche Komplexität wie ImmutableSortedSet<T>, da beide binäre Bäume verwenden. Der wesentliche Unterschied besteht darin, dass ImmutableSortedSet<T> einen unveränderlichen binären Baum verwendet. Da ImmutableSortedSet<T> auch eine System.Collections.Immutable.ImmutableSortedSet<T>.Builder Klasse bietet, die Mutationen zulässt, können Sie sowohl Unveränderlichkeit als auch Leistung erreichen.

Verwandte Artikel

Referenz

• System.Array
• System.Collections
• System.Collections.Concurrent
• System.Collections.Generic
• System.Collections.Specialized
• System.Linq
• System.Collections.Immutable