Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen Versionsunterschied
VisuellWikitext
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Keine Bearbeitungszusammenfassung
LeonH (Diskussion | Beiträge)
sopra
126 Bearbeitungen
Keine Bearbeitungszusammenfassung
 
(44 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Stub}}
{{UEA|Dietsch|Hier sollte noch ein einleitender Text stehen}}
{{löschen}}
{{Navi:Implementierung}}
== Hinweise ==
* Falls nicht anders angegeben sind Laufzeiten immer Average Case.
*Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung].
*Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|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 [http://msdn.microsoft.com/en-us/library/bb383977.aspx Extension Method]. Bei Strukturen die das Interface [http://msdn.microsoft.com/en-us/library/5y536ey6.aspx IList&lt;T&gt;] 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. <ref>[http://msdn.microsoft.com/en-us/library/bb299233.aspx Enumerable.ElementAt&lt;TSource&gt; Method]</ref>
*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.


== Hinweise  ==
== Laufzeiten und Eigenschaften (nach [http://msdn.microsoft.com/en-us/ MSDN]) ==
* ''n'' entspricht immer dem ''Count'' der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
* Falls nicht anders angegeben sind Laufzeiten immer Average Case.
* Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung].  
* Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|Generics]]. Ihre Verwendung wird im [[Generic]]-Artikel erklärt.
* Mit ''Element-Typ'' wird hier der Wert bezeichnet, den der [[CSharp:Enumerator|Enumerator]] bei einer [[CSharp:foreach|foreach]]-Anweisung zurückgibt.
* 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 [http://msdn.microsoft.com/en-us/ MSDN]) ==
=== ein-elementige Datenstrukturen ===
=== ... ===


{| class="default"
{| class="default"
|-
|-
| class="blank" | <br>
! colspan="6" | Laufzeiten von Methoden
| class="blank" | <br>
| class="blank" | <br>
! colspan="6" | Laufzeiten
| colspan="3" class="blank" | <br>
|-
| class="blank" | <br>
! width="50px"| Add
! Remove
! ElementAt
! Contains
! Clear
! Count
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
| O(1) <br> O(n)<ref name="countlargercapacity"> Wenn Count + 1 > Capacity.</ref>
| O(1)
| O(n)
| O(1)
| O(n)
| O(1)
| T
| Nein
| class="close" | keine Duplikate<br>
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
| O(1)
| O(1)
| O(n)
| O(n)
| O(n)
| O(1)
| T
| Nein
| class="close" |
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(n)
| O(1)
| O(n)
| O(n)
| O(1)
| T
| Nein
| class="close" |
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(1)<br>
| O(n)<br>
| O(n)<br>
| O(n)<br>
| O(1)<br>
| T<br>
| Nein<br>
| class="close" |
Remove und Add sind Deqeue und Enqueue
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(1)<br>
| O(n)<br>
| O(n)<br>
| O(n)<br>
| O(1)<br>
| T<br>
| Nein<br>
| class="close" | Remove und Add sind Pop und Push<br>
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(n)<br>
| O(1)<br>
| O(n)<br>
| O(n)<br>
| O(1)<br>
| T<br>
| Ja<br>
| class="close" | benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen um [[ThreadSafety|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 [http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx Item-Property] der Datenstruktur angesprochen werden:<br><source lang="csharp">myDataStructure[key] = expression;</source>Dabei wird ein Wert
** wenn der Key bereits vorhanden ist überschrieben
** wenn der Key noch nicht vorhanden ist neu angelegt.
* Sie implementieren das [http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx IDictionary]-Interface.
* Die Laufzeit für <tt>ElementAt</tt> ist für alle außer <tt>Hashtable</tt> O(n). <tt>Hashtable</tt> unterstützt diese Methode nicht.
Außerdem sortieren sowohl <tt>SortedDictionary<TKey,TValue></tt> als auch <tt>SortedList<TKey,TValue></tt> 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 <tt>TKey</tt>, der das Interface [http://msdn.microsoft.com/en-us/library/8ehhxeaf.aspx IComparer<T>] erfüllt.
{| class="default"
|-
| class="blank" |
! colspan="5" | Laufzeiten
| colspan="3" class="blank" | <br>
|-
|-
| class="blank" | <br>
| class="blank" |  
! Add  
! width="50px" | Add  
! Remove  
! Remove  
! ElementAt
! ContainsKey
! Contains
! Clear  
! Clear  
! Count  
! Count  
Zeile 29: Zeile 203:
! Bemerkungen
! Bemerkungen
|-
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]  
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(1)  
| O(1)  
| &nbsp;?
| O(1)  
| O(1)  
| O(n)  
| O(n)  
| O(1)  
| O(1)  
| T
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein  
| Nein  
| class="close" | keine Duplikate<br>keine Ordnung
| class="close" | Verfügt über [[TryGetValue]]-Methode
|-
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]  
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| O(1)<br>
| O(log n)  
| O(1)<br>
| O(log n)  
| O(n)<br>
| O(log n)  
| O(n)<br>
| O(n)  
| O(1)<br>
| O(1)  
| O(1)<br>
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| T<br>  
| Nein  
| Nein<br>
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten
| class="close" | Ordnung<br>Duplikate<br>
|-
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]  
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>  
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(n)<br>
| O(1)
| O(1)<br>
| O(1)
| O(n)<br>
| O(n)  
| <br>
| O(1)
| O(1)<br>  
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<object,object>]<br>oder<br>[http://msdn.microsoft.com/en-us/library/system.collections.dictionaryentry.aspx DictionaryEntry]
| T<br>  
| Read-Only mit einem schreibenden Thread
| Nein<br>
| class="close" | Die initiale Capacity der Hashtable kann im [[Konstruktor]] angegeben werden: [http://msdn.microsoft.com/en-us/library/k3x9ky40.aspx <tt>Hashtable(Int32)</tt>]
| class="close" | <br>
|-
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]  
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>  
| O(n)
| <br>  
| O(n)
| <br>  
| O(log n)
| <br>  
| O(n)
| <br>  
| O(1)
| <br>  
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| T<br>  
| Nein
| Nein<br>  
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten
| class="close" | <br>
|} [[Kategorie:Code-Beispiele]]
 
== Laufzeiten nach eigenen Tests in ms ==
Alle Eigenschaften und Bemerkungen aus der vorherigen Sektion gelten auch hier.
 
Das ursprüngliche Logfile kann [[Media:datastructure_speed_log.txt|hier]] eingesehen werden.
 
Die Messungen wurden mit folgenden Parametern durchgeführt:
* erste Messung: Elemente vom Typ Int32
** Alle Messungen wurden mit <tt>System.Diagnostics.Stopwatch</tt> 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 Messungen Add (mit [[foreach]]), Remove (mit [[for]]), ElementAt (mit [[for]]) und Contains (mit [[for]]) aus diesem Array extrahiert.
* zweite Messung: Elemente vom Typ Testobject (Objekt das ein Attribut <tt>value</tt> (Int32) besitzt und dieses für Vergleiche und Hashcode benutzt)
** Alle Messungen wurden mit <tt>System.Diagnostics.Stopwatch</tt> durchgeführt.
** Es wurden 100.000 zufällige und disjunkte Objekte erzeugt (mit <tt>value</tt> zwischen 0 und Int32.Max) und in einem Array gespeichert.
** Diese Objekte wurden für die Messungen Add (mit [[foreach]]), Remove (mit [[for]]), ElementAt (mit [[for]]) und Contains (mit [[for]]) aus diesem Array extrahiert.
 
=== Int32 (value-type) ===
==== ein-elementige Datenstrukturen  ====
 
{| class="default"
|-
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| class="blank" | <br>
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity <br>
| O(1)<br>  
! colspan="6" | Laufzeiten
| <br>
| <br>
 
| <br>
| <br>
| T<br>
| Nein<br>
| class="close" | <br>
|-
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]  
| class="blank" | <br>
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>  
| O(n)<br>  
! Add
| O(1)<br>  
| O(n)<br>  
! Remove
| <br>  
| O(1)<br>  
! ElementAt
| T<br>  
| Ja<br>  
! Contains
| class="close" | benutzt intern List&lt;T&gt;<br>
! Clear
! Count
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
| 10ms / 3ms
| 4ms
| 47.672ms
| 5ms
| 0ms <ref name="clear">Clear scheint in den aktuellen Tests immer 0ms zu brauchen, die Ursache könnte bei falschen Tests oder dem [[Garbage Collector]] liegen.</ref>
| class="close" | 2ms <ref name="count">Die hier angegebene Zeit ist irrelevant, da der Test hier nur das Zuweisen eines [[Property]]-Werts an eine Variable misst.</ref>
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
| 7ms / 4ms
| 28.681ms
| 63.373ms
| 28.655ms
| 0ms <ref name="clear"/>
| class="close" | 2ms <ref name="count"/>
 
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| 2ms / 1ms
| 5.829ms
| 2ms
| 30.745ms
| 0ms <ref name="clear"/>
| class="close" | 2ms <ref name="count"/>
 
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
| 2ms / 1ms
| 1ms<ref name="removefirst">Diese Datenstruktur unterstützt nur das Entfernen des ersten Elements, d.h. in diesem Test wurde n-mal das erste Element entfernt.</ref><br>
| 75.194ms<br>
| 123.220ms<br>
| 0ms <ref name="clear"/>
| class="close" | 12ms <ref name="countenumerate">Der hier angegebene Wert bezieht sich auf die Extension-Methode Count(), die von Enumerate bereitgestellt wird.</ref>
 
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| 1ms
| 1ms<ref name="removefirst" /><br>
| 48.820ms
| 95.852ms
| 0ms <ref name="clear"/>
| class="close" | 10ms<ref name="countenumerate"/>
 
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
| 8ms / 7ms
| 96.966ms
| 9ms
| 29.295ms
| 0ms <ref name="clear"/>
| class="close" | 8ms <ref name="count"/>
 
|}
|}


=== ...  ===
==== zwei-elementige Datenstrukturen  ====
 
{| class="default"
|-
| class="blank" |
! colspan="5" | Laufzeiten
 
|-
| class="blank" |
! Add
! Remove
! ContainsKey
! Clear
! Count
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]
| 8ms / 4ms
| 3ms
| 4ms
| 0ms <ref name="clear"/>
| class="close" | 0ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| 50ms
| 59ms
| 30ms
| 0ms <ref name="clear"/>
| class="close" | 0ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
| 24ms / 10ms
| 9ms
| 8ms
| 0ms <ref name="clear"/>
| class="close" | 0ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| 3.190ms
| 3.147ms
| 20ms
| 0ms <ref name="clear"/>
| class="close" | 0ms <ref name="count"/>
|}
 
=== Testobject (reference-Typ) ===
==== ein-elementige Datenstrukturen ====


{| class="default"
{| class="default"
|-
|-
| class="blank" | <br>
| class="blank" | <br>
! colspan="6" | Laufzeiten von Methoden
| class="blank" | <br>
! colspan="6" | Laufzeiten
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
! Add
! Add
! Remove
! Remove
! ElementAt
! ElementAt
! Contains
! Contains
! Clear
! Clear
! Count
! Count
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
|-
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| O(1)<br>
| 19ms / 13ms
| <br>
| O(1)<br>
| 13ms
| <br>
| <br>
| 76.329ms
| <br>
| Nein<br>
| 14ms
| class="close" | <br>
| 0ms <ref name="clear"/>
| class="close" | 3ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
| 15ms / 5ms
| 60.987ms
| 83.695ms
| 53.370ms
| 0ms <ref name="clear"/>
| class="close" | 3ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| 2ms / 2ms
| 42.624ms
| 3ms
| 52.683ms
| 0ms <ref name="clear"/>
| class="close" | 3ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
| 6ms / 1ms
| 1ms <ref name="removefirst"/>
| 80.020ms
| 183.873ms
| 0ms <ref name="clear"/>
| class="close" | 137.493ms <ref name="countenumerate"/>
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| 2ms
| 1ms<ref name="removefirst" />
| 75.154ms
| 167.390ms
| 0ms <ref name="clear"/>
| class="close" | 128.508ms <ref name="countenumerate"/>
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
| 9ms / 8ms
| 60.109ms
| 9ms
| 62.040ms
| 0ms <ref name="clear"/>
 
| class="close" | 9ms <ref name="count"/>
 
|}
 
==== zwei-elementige Datenstrukturen  ====
 
{| class="default"
|-
| class="blank" |
! colspan="5" | Laufzeiten
 
|-
| class="blank" |
! Add
! Remove
! ContainsKey
! Clear
! Count
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]
| 19ms / 13ms
| 13ms
| 14ms
| 0ms <ref name="clear"/>  
| class="close" | 1ms <ref name="count"/>
|-
|-
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| O(log n)<br>
| 155ms / 150ms
| O(log n)<br>
| 162ms
| <br>
| 139ms
| O(log n)<br>
| 0ms <ref name="clear"/>
| <br>
| class="close" | 1ms <ref name="count"/>
| <br>
| <br>
| Nein<br>
| class="close" | schneller als SortedList bei unsortierten Daten<br>
|-
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
| <br>
| 25ms
| <br>
| 14ms
| <br>
| 13ms
| <br>
| 0ms <ref name="clear"/>  
| <br>
| class="close" | 0ms <ref name="count"/>
| <br>
| <br>
| Read-Only mit einem schreibenden Thread<br>
| class="close" | <br>
|-
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| O(n)<br>
| 8.891ms
| O(n)<br>
| 9.025ms
| <br>
| 117ms
| O(log n)<br>
| 0ms <ref name="clear"/>
| <br>
| class="close" | 1ms <ref name="count"/>
| <br>
| <br>
| Nein<br>
| class="close" | schneller als SortedDictionary bei vorsortierten Daten<br>
|}
|}


[[Category:CSharp]]
[[Kategorie:Code-Beispiele]]
 
== Referenzen ==
<references />
 
 
[[Category:CSharp]] [[Kategorie:Code-Beispiele]]
[[Kategorie:Begriffe]]

Aktuelle Version vom 21. Oktober 2020, 13:23 Uhr

Vorlage:Navi:Implementierung

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:
    myDataStructure[key] = expression;
    Dabei wird ein Wert
    • 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.

Das ursprüngliche Logfile kann hier eingesehen werden.

Die Messungen wurden mit folgenden Parametern durchgeführt:

  • erste Messung: 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 Messungen Add (mit foreach), Remove (mit for), ElementAt (mit for) und Contains (mit for) aus diesem Array extrahiert.
  • zweite Messung: 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 Messungen 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] 10ms[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> 8ms / 4ms 3ms 4ms 0ms [3] 0ms [4]
SortedDictionary<TKey, TValue> 50ms 59ms 30ms 0ms [3] 0ms [4]
Hashtable 24ms / 10ms 9ms 8ms 0ms [3] 0ms [4]
SortedList<TKey, TValue> 3.190ms 3.147ms 20ms 0ms [3] 0ms [4]

Testobject (reference-Typ)

ein-elementige Datenstrukturen


 Laufzeiten



Add Remove ElementAt Contains Clear Count
HashSet<T> 19ms / 13ms 13ms 76.329ms 14ms 0ms [3] 3ms [4]
LinkedList<T> 15ms / 5ms 60.987ms 83.695ms 53.370ms 0ms [3] 3ms [4]
List<T> 2ms / 2ms 42.624ms 3ms 52.683ms 0ms [3] 3ms [4]
Queue<T> 6ms / 1ms 1ms [5] 80.020ms 183.873ms 0ms [3] 137.493ms [6]
Stack<T> 2ms 1ms[5] 75.154ms 167.390ms 0ms [3] 128.508ms [6]
SynchronizedCollection<T> 9ms / 8ms 60.109ms 9ms 62.040ms 0ms [3] 9ms [4]

zwei-elementige Datenstrukturen

Laufzeiten
Add Remove ContainsKey Clear Count
Dictionary<TKey, TValue> 19ms / 13ms 13ms 14ms 0ms [3] 1ms [4]
SortedDictionary<TKey, TValue> 155ms / 150ms 162ms 139ms 0ms [3] 1ms [4]
Hashtable 25ms 14ms 13ms 0ms [3] 0ms [4]
SortedList<TKey, TValue> 8.891ms 9.025ms 117ms 0ms [3] 1ms [4]

Referenzen

  1. ↑ Enumerable.ElementAt<TSource> Method
  2. ↑ 2,0 2,1 2,2 2,3 2,4 2,5 2,6 Wenn Count + 1 > Capacity.
  3. ↑ 3,00 3,01 3,02 3,03 3,04 3,05 3,06 3,07 3,08 3,09 3,10 3,11 3,12 3,13 3,14 3,15 3,16 3,17 3,18 3,19 Clear scheint in den aktuellen Tests immer 0ms zu brauchen, die Ursache könnte bei falschen Tests oder dem Garbage Collector liegen.
  4. ↑ 4,00 4,01 4,02 4,03 4,04 4,05 4,06 4,07 4,08 4,09 4,10 4,11 4,12 4,13 4,14 4,15 Die hier angegebene Zeit ist irrelevant, da der Test hier nur das Zuweisen eines Property-Werts an eine Variable misst.
  5. ↑ 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. ↑ 6,0 6,1 6,2 6,3 Der hier angegebene Wert bezieht sich auf die Extension-Methode Count(), die von Enumerate bereitgestellt wird.
Abgerufen von „https://sopranium.de/index.php?title=Datenstrukturen&oldid=9651“