Datenstrukturen: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
| Zeile 51: | Zeile 51: | ||
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>] | ! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>] | ||
| O(1) <br> O(n)<ref name="countlargercapacity" /> | | O(1) <br> O(n)<ref name="countlargercapacity"> Wenn Count + 1 > Capacity.</ref> | ||
| O(1) | | O(1) | ||
Version vom 20. April 2009, 09:21 Uhr
Hinweise
- Falls nicht anders angegeben sind Laufzeiten immer Average Case.
- Alle Links zu den Datenstrukturen zeigen auf die englische Version der MSDN. Diese ist typischerweise vollständiger und genauer als ihre deutsche Übersetzung.
- Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind Generics. Ihre Verwendung wird im Generic-Artikel erklärt.
- n entspricht immer dem Count der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
- Mit Element-Typ wird hier der Wert bezeichnet, den der Enumerator bei einer Foreach-Anweisung zurückgibt.
- ElementAt ist eine spezielle Extension Method. Bei Strukturen die das Interface IList<T> implementieren gibt sie das Element an der angegebenen Position an, ansonsten iteriert sie so oft wie angegeben und gibt das Element an dieser Stelle zurück. [1]
- Datenstrukturen die auf Arrays basieren besitzen intern eine Capacity. Diese gibt die aktuelle Größe des internen Arrays an. Capacity ist immer größer bzw. gleich Count. Sollte beim Hinzufügen eines Elements die Capacity der Struktur überschritten werden, muss diese wachsen. Dazu erzeugt sie intern einen neuen, größeren Array und kopiert alle bis dahin vorhandenen Einträge in diesen neuen Array. Typischerweise ist die neue Größe des Arrays die erste Primzahl, die größer als das Doppelte der alten Capacity ist.
Laufzeiten und Eigenschaften (nach MSDN)
ein-elementige Datenstrukturen
| Laufzeiten | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Add | Remove | ElementAt | Contains | Clear | Count | Element-Typ | Thread-safe | Bemerkungen | |
| HashSet<T> | O(1) O(n)[2] |
O(1) | O(n) | O(1) | O(n) | O(1) | T | Nein | keine Duplikate |
| LinkedList<T> | O(1) | O(1) | O(n) | O(n) | O(n) | O(1) | T | Nein | |
| List<T> | O(1) O(n)[2] |
O(n) | O(1) | O(n) | O(n) | O(1) | T | Nein | |
| Queue<T> | O(1) O(n)[2] |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
T |
Nein |
Remove und Add sind Deqeue und Enqueue
|
| Stack<T> | O(1) O(n)[2] |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
T |
Nein |
Remove und Add sind Pop und Push |
| SynchronizedCollection<T> | O(1) O(n)[2] |
O(n) |
O(1) |
O(n) |
O(n) |
O(1) |
T |
Ja |
benutzt intern List<T>, hat aber zusätzliche Mechanismen um Thread-safety zu garantieren |
zwei-elementige Datenstrukturen
Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:
- Keys müssen eindeutig sein.
- Keys dürfen nicht von "außen" verändert werden (immutable).
- Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
- Die Values können über die Item-Property der Datenstruktur angesprochen werden:Dabei wird ein Wert
myDataStructure[key] = expression;
- wenn der Key bereits vorhanden ist überschrieben
- wenn der Key noch nicht vorhanden ist neu angelegt.
- Sie implementieren das IDictionary-Interface.
- Die Laufzeit für ElementAt ist für alle außer Hashtable O(n). Hashtable unterstützt diese Methode nicht.
Außerdem sortieren sowohl SortedDictionary<TKey,TValue> als auch SortedList<TKey,TValue> ihren Inhalt beim einfügen, d.h. wenn man mit einer foreach-Anweisung (o.ä.) über sie iteriert, erhält man die Elemente geordnet zurück. Dabei wird die Ordnung durch den beim Erzeugen angegebenen Comparer bestimmt. Wird kein spezieller Comparer angegeben, verwenden sie einen Standard-Comparer für TKey, der das Interface IComparer<T> erfüllt.
| Laufzeiten | ||||||||
|---|---|---|---|---|---|---|---|---|
| Add | Remove | ContainsKey | Clear | Count | Element-Typ | Thread-safe | Bemerkungen | |
| Dictionary<TKey, TValue> | O(1) O(n)[2] |
O(1) | O(1) | O(n) | O(1) | KeyValuePair<TKey,TValue> | Nein | Verfügt über TryGetValue-Methode |
| SortedDictionary<TKey, TValue> | O(log n) | O(log n) | O(log n) | O(n) | O(1) | KeyValuePair<TKey,TValue> | Nein | Verfügt über TryGetValue-Methode schneller als SortedList bei unsortierten Daten |
| Hashtable | O(1) O(n)[2] |
O(1) | O(1) | O(n) | O(1) | KeyValuePair<object,object> oder DictionaryEntry |
Read-Only mit einem schreibenden Thread | Die initiale Capacity der Hashtable kann im Konstruktor angegeben werden: Hashtable(Int32) |
| SortedList<TKey, TValue> | O(n) | O(n) | O(log n) | O(n) | O(1) | KeyValuePair<TKey,TValue> | Nein | Verfügt über TryGetValue-Methode schneller als SortedDictionary bei vorsortierten Daten |
Laufzeiten nach eigenen Tests in ms
Alle Eigenschaften und Bemerkungen aus der vorherigen Sektion gelten auch hier.
Der Quellcode des für die Tests verwendeten Miniprogramms kann hier eingesehen werden, das ursprüngliche Logfile hier.
Die Tests wurden mit folgenden Parametern durchgeführt:
- erster Test: Elemente vom Typ Int32
- Alle Messungen wurden mit System.Diagnostics.Stopwatch durchgeführt.
- Es wurden 100.000 zufällige und disjunkte Werte erzeugt (zwischen 0 und Int32.Max) und in einem Array gespeichert.
- Diese Werte wurden für die Tests Add (mit foreach), Remove (mit for), ElementAt (mit for) und Contains (mit for) aus diesem Array extrahiert.
- zweiter Test: Elemente vom Typ Testobject (Objekt das ein Attribut value (Int32) besitzt und dieses für Vergleiche und Hashcode benutzt)
- Alle Messungen wurden mit System.Diagnostics.Stopwatch durchgeführt.
- Es wurden 100.000 zufällige und disjunkte Objekte erzeugt (mit value zwischen 0 und Int32.Max) und in einem Array gespeichert.
- Diese Objekte wurden für die Tests Add (mit foreach), Remove (mit for), ElementAt (mit for) und Contains (mit for) aus diesem Array extrahiert.
Int32 (value-type)
ein-elementige Datenstrukturen
| Laufzeiten | |||||||
|---|---|---|---|---|---|---|---|
| Add | Remove | ElementAt | Contains | Clear | Count | ||
| HashSet<T> | 10ms / 3ms | 4ms | 47.672ms | 5ms | 0ms [3] | 2ms [4] | |
| LinkedList<T> | 7ms / 4ms | 28.681ms | 63.373ms | 28.655ms | 0ms [3] | 2ms [4] | |
| List<T> | 2ms / 1ms | 5.829ms | 2ms | 30.745ms | 0ms [3] | 2ms [4] | |
| Queue<T> | 2ms / 1ms | 1ms[5] |
75.194ms |
123.220ms |
0ms [3] | 12ms [6] | |
| Stack<T> | 1ms | 1ms[5] |
48.820ms | 95.852ms | 0ms [3] | 100.355ms[6] | |
| SynchronizedCollection<T> | 8ms / 7ms | 96.966ms | 9ms | 29.295ms | 0ms [3] | 8ms [4] | |
zwei-elementige Datenstrukturen
| Laufzeiten | ||||||
|---|---|---|---|---|---|---|
| Add | Remove | ContainsKey | Clear | Count | ||
| Dictionary<TKey, TValue> | O(1) O(n) wenn Count + 1 > Capacity |
O(1) | O(1) | O(n) | O(1) | |
| SortedDictionary<TKey, TValue> | O(log n) | O(log n) | O(log n) | O(n) | O(1) | |
| Hashtable | O(1) O(n) wenn Count + 1 > Capacity |
O(1) | O(1) | O(n) | O(1) | |
| SortedList<TKey, TValue> | O(n) | O(n) | O(log n) | O(n) | O(1) | |
Testobject (reference-Typ)
ein-elementige Datenstrukturen
| Laufzeiten | |||||||
|---|---|---|---|---|---|---|---|
| Add | Remove | ElementAt | Contains | Clear | Count | ||
| HashSet<T> | 10ms / 4ms | 4ms | 48.240ms | 4ms | 0ms | 0ms | |
| LinkedList<T> | 7ms | 28.883ms | 63.349ms | 58.970ms | 0ms | 0ms | |
| List<T> | 2ms | 5848ms | 2ms | 61.034ms | 0ms | 0ms | |
| Queue<T> | 2ms / 1ms | 1ms[5] |
76.947ms |
204.310ms |
0ms |
0ms | |
| Stack<T> | 1ms |
1ms[5] |
53.155ms |
192.108ms |
0ms |
0ms | |
| SynchronizedCollection<T> | 8ms / 7ms |
101.157ms |
9ms |
59.859ms |
0ms |
0ms | |
zwei-elementige Datenstrukturen
| Laufzeiten | ||||||
|---|---|---|---|---|---|---|
| Add | Remove | ContainsKey | Clear | Count | ||
| Dictionary<TKey, TValue> | O(1) O(n) wenn Count + 1 > Capacity |
O(1) | O(1) | O(n) | O(1) | |
| SortedDictionary<TKey, TValue> | O(log n) | O(log n) | O(log n) | O(n) | O(1) | |
| Hashtable | O(1) O(n) wenn Count + 1 > Capacity |
O(1) | O(1) | O(n) | O(1) | |
| SortedList<TKey, TValue> | O(n) | O(n) | O(log n) | O(n) | O(1) | |
Referenzen
- ↑ Enumerable.ElementAt<TSource> Method
- ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 Wenn Count + 1 > Capacity.
- ↑ 3,0 3,1 3,2 3,3 3,4 3,5 Clear scheint in den aktuellen Tests immer 0ms zu brauchen, die Ursache könnte bei falschen Tests oder dem Garbage Collector liegen.
- ↑ 4,0 4,1 4,2 4,3 Die hier angegebene Zeit ist irrelevant, da der Test hier nur das Zuweisen eines Property-Werts an eine Variable misst.
- ↑ 5,0 5,1 5,2 5,3 Diese Datenstruktur unterstützt nur das Entfernen des ersten Elements, d.h. in diesem Test wurde n-mal das erste Element entfernt.
- ↑ 6,0 6,1 Der hier angegebene Wert bezieht sich auf die Extension-Methode Count(), die von Enumerate bereitgestellt wird.
