Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen Versionsunterschied
LeonH (Diskussion | Beiträge)
sopra
126 Bearbeitungen
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
 
(27 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
{{Stub}}
{{UEA|Dietsch|Hier sollte noch ein einleitender Text stehen}}
 
{{löschen}}
== Hinweise ==
{{Navi:Implementierung}}
 
== Hinweise ==
*Falls nicht anders angegeben sind Laufzeiten immer Average Case.  
* 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].  
*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].  
Zeile 26: Zeile 26:
   
   
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
| colspan="3" class="blank" | <br>
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
   
   
! Add
! width="50px"| Add
   
   
! Remove
! Remove
Zeile 51: Zeile 51:
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| O(1) <br> O(n)<ref name="countlargercapacity"> Wenn Count + 1 > Capacity.</ref>
 
| O(1)
| O(1)
   
   
Zeile 91: Zeile 91:
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| O(1)<br>O(n)<ref name="countlargercapacity" />
   
   
| O(n)
| O(n)
Zeile 111: Zeile 111:
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| O(1)<br>O(n)<ref name="countlargercapacity" />
   
   
| O(1)<br>
| O(1)<br>
Zeile 134: Zeile 134:
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity <br>
| O(1)<br>O(n)<ref name="countlargercapacity" />
   
   
| O(1)<br>
| O(1)<br>
Zeile 154: Zeile 154:
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| O(1)<br>O(n)<ref name="countlargercapacity" />
   
   
| O(n)<br>
| O(n)<br>
Zeile 170: Zeile 170:
| Ja<br>
| Ja<br>
   
   
| class="close" |  
| class="close" | benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen um [[ThreadSafety|Thread-safety]] zu garantieren
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen<br>um [[ThreadSafety|Thread-safety]] zu garantieren
 
|}
|}


Zeile 194: Zeile 191:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |  
| colspan="3" class="blank" | <br>
|-
|-
| class="blank" |  
| class="blank" |  
! Add  
! width="50px" | Add  
! Remove  
! Remove  
! ContainsKey  
! ContainsKey  
Zeile 207: Zeile 204:
|-
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&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)  
| O(1)  
| O(1)  
Zeile 227: Zeile 224:
|-
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
| O(1)<br>O(n) wenn Count + 1 > Capacity
| O(1)<br>O(n)<ref name="countlargercapacity" />
| O(1)
| O(1)
| O(1)
| O(1)
Zeile 248: Zeile 245:


== Laufzeiten nach eigenen Tests in ms ==
== Laufzeiten nach eigenen Tests in ms ==
Der Quellcode des für die Tests verwendeten Miniprogramms kann [[DatenstrukturenSpeedTest|hier]] eingesehen werden.
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  ====


=== ein-elementige Datenstrukturen  ===
{| class="default"
{| class="default"
|-
|-
Zeile 257: Zeile 268:
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
   
   
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
Zeile 272: Zeile 283:
   
   
! Count
! 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
   
   
! Element-Typ
| 28.681ms
| 63.373ms
| 28.655ms
   
   
! [[ThreadSafety|Thread-safe]]
| 0ms <ref name="clear"/>
   
   
! Bemerkungen
| class="close" | 2ms <ref name="count"/>
 
|-
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| 2ms / 1ms
| 5.829ms
| 2ms
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| 30.745ms
   
   
| O(1)
| 0ms <ref name="clear"/>
   
   
| O(n)
| class="close" | 2ms <ref name="count"/>
 
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
   
   
| O(1)
| 2ms / 1ms
   
   
| O(n)
| 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>
   
   
| O(1)
| 75.194ms<br>
   
   
| T
| 123.220ms<br>
   
   
| Nein
| 0ms <ref name="clear"/>
   
   
| class="close" | keine Duplikate<br>
| 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/he2s3bh7.aspx LinkedList&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| 1ms
| 1ms<ref name="removefirst" /><br>
| 48.820ms
   
   
| O(1)
| 95.852ms
   
   
| O(1)
| 0ms <ref name="clear"/>
   
   
| O(n)
| class="close" | 10ms<ref name="countenumerate"/>
 
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
   
   
| O(n)
| 8ms / 7ms
   
   
| O(n)
| 96.966ms
   
   
| O(1)
| 9ms
   
   
| T
| 29.295ms
   
   
| Nein
| 0ms <ref name="clear"/>
   
   
| class="close" |  
| 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"
|-
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| class="blank" | <br>
! colspan="6" | Laufzeiten
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
 
|-
| class="blank" | <br>
   
   
| O(n)
! Add
   
   
| O(1)
! Remove
   
   
| O(n)
! ElementAt
   
   
| O(n)
! Contains
   
   
| O(1)
! Clear
   
   
| T
! Count
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
   
   
| Nein
| 19ms / 13ms
   
   
| class="close" |
| 13ms
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| 76.329ms
   
   
| O(1)<br>
| 14ms
   
   
| O(n)<br>
| 0ms <ref name="clear"/>
   
   
| O(n)<br>
| class="close" | 3ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
   
   
| O(n)<br>
| 15ms / 5ms
   
   
| O(1)<br>
| 60.987ms
   
   
| T<br>
| 83.695ms
   
   
| Nein<br>
| 53.370ms
   
   
| class="close" |
| 0ms <ref name="clear"/>
Remove und Add sind Deqeue und Enqueue
   
   
 
| class="close" | 3ms <ref name="count"/>
|-
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| 2ms / 2ms
| 42.624ms
| 3ms
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity <br>
| 52.683ms
   
   
| O(1)<br>
| 0ms <ref name="clear"/>
   
   
| O(n)<br>
| class="close" | 3ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
   
   
| O(n)<br>
| 6ms / 1ms
   
   
| O(n)<br>
| 1ms <ref name="removefirst"/>
   
   
| O(1)<br>
| 80.020ms
   
   
| T<br>
| 183.873ms
   
   
| Nein<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | Remove und Add sind Pop und Push<br>
| class="close" | 137.493ms <ref name="countenumerate"/>
|-
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| 2ms
   
   
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| 1ms<ref name="removefirst" />
   
   
| O(n)<br>
| 75.154ms
   
   
| O(1)<br>
| 167.390ms
   
   
| O(n)<br>
| 0ms <ref name="clear"/>
   
   
| O(n)<br>
| class="close" | 128.508ms <ref name="countenumerate"/>
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
   
   
| O(1)<br>
| 9ms / 8ms
   
   
| T<br>
| 60.109ms
   
   
| Ja<br>
| 9ms
   
   
| class="close" |
| 62.040ms
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen<br>um [[ThreadSafety|Thread-safety]] zu garantieren
   
   
| 0ms <ref name="clear"/>
| class="close" | 9ms <ref name="count"/>


|}
|}


=== zwei-elementige Datenstrukturen  ===
==== zwei-elementige Datenstrukturen  ====


{| class="default"
{| class="default"
Zeile 412: Zeile 529:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |
 
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 420: Zeile 537:
! 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/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| 19ms / 13ms
| O(1)
| 13ms
| O(1)
| 14ms
| O(n)
| 0ms <ref name="clear"/>  
| O(1)
| class="close" | 1ms <ref name="count"/>
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode
|-
|-
! [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)
| 155ms / 150ms
| O(log n)
| 162ms
| O(log n)
| 139ms
| O(n)
| 0ms <ref name="clear"/>
| O(1)
| class="close" | 1ms <ref name="count"/>
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten
|-
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]  
| O(1)<br>O(n) wenn Count + 1 > Capacity
| 25ms
| O(1)
| 14ms
| O(1)
| 13ms
| O(n)
| 0ms <ref name="clear"/>  
| O(1)
| class="close" | 0ms <ref name="count"/>
| [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]
| Read-Only mit einem schreibenden Thread
| 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>]
|-
|-
! [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)
| 8.891ms
| O(n)
| 9.025ms
| O(log n)
| 117ms
| O(n)
| 0ms <ref name="clear"/>
| O(1)
| class="close" | 1ms <ref name="count"/>
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
|}
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten
|} [[Kategorie:Code-Beispiele]]


[[Kategorie:Code-Beispiele]]


== Referenzen ==
== Referenzen ==
Zeile 471: Zeile 574:


[[Category:CSharp]] [[Kategorie:Code-Beispiele]]
[[Category:CSharp]] [[Kategorie:Code-Beispiele]]
[[Kategorie:Begriffe]]
Abgerufen von „https://sopranium.de/Datenstrukturen“