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
LeonH (Diskussion | Beiträge)
sopra
126 Bearbeitungen
Keine Bearbeitungszusammenfassung
 
(21 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 250: Zeile 247:
Alle Eigenschaften und Bemerkungen aus der vorherigen Sektion gelten auch hier.  
Alle Eigenschaften und Bemerkungen aus der vorherigen Sektion gelten auch hier.  


Der Quellcode des für die Tests verwendeten Miniprogramms kann [[DatenstrukturenSpeedTest|hier]] eingesehen werden, das ursprüngliche Logfile [[Media:datastructure_speed_log.txt|hier]].
Das ursprüngliche Logfile kann [[Media:datastructure_speed_log.txt|hier]] eingesehen werden.


Die Tests wurden mit folgenden Parametern durchgeführt:  
Die Messungen wurden mit folgenden Parametern durchgeführt:  
* erster Test: Elemente vom Typ Int32
* erste Messung: Elemente vom Typ Int32
** Alle Messungen wurden mit <tt>System.Diagnostics.Stopwatch</tt> durchgeführt.
** 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.
** 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.  
** Diese Werte wurden für die Messungen 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 <tt>value</tt> (Int32) besitzt und dieses für Vergleiche und Hashcode benutzt)
* 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.
** 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.
** 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 Tests Add (mit [[foreach]]), Remove (mit [[for]]), ElementAt (mit [[for]]) und Contains (mit [[for]]) aus diesem Array extrahiert.
** 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) ===
=== Int32 (value-type) ===
Zeile 271: Zeile 268:
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
   
   
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
Zeile 287: Zeile 284:
! Count
! Count
|-
|-
! [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;]  
| 10ms / 3ms
| 10ms / 4ms
| 4ms  
| 47.672ms
| 4ms
| 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>
| 48.240ms
| 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>
| 4ms
| 0ms
| class="close" | 0ms
|-
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
   
   
| 7ms
| 7ms / 4ms
   
   
| 28.883ms
| 28.681ms
   
   
| 63.349ms
| 63.373ms
   
   
| 58.970ms
| 28.655ms
   
   
| 0ms
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms
| class="close" | 2ms <ref name="count"/>
 
|-
|-
! [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;]
   
   
| 2ms
| 2ms / 1ms
   
   
| 5848ms
| 5.829ms
   
   
| 2ms
| 2ms
   
   
| 61.034ms
| 30.745ms
   
   
| 0ms
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms
| class="close" | 2ms <ref name="count"/>
 
|-
|-
! [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;]
   
   
| 2ms /&nbsp;1ms
| 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>
| 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>
   
   
| 76.947ms<br>
| 75.194ms<br>
   
   
| 204.310ms<br>
| 123.220ms<br>
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms<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/3278tedw.aspx Stack&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
   
   
| 1ms <br>
| 1ms
   
   
| 1ms<ref name="removefirst" /><br>
| 1ms<ref name="removefirst" /><br>
   
   
| 53.155ms<br>
| 48.820ms
   
   
| 192.108ms<br>
| 95.852ms
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms<br>
| class="close" | 10ms<ref name="countenumerate"/>
 
|-
|-
! [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;]
   
   
| 8ms /&nbsp;7ms<br>
| 8ms / 7ms
   
   
| 101.157ms<br>
| 96.966ms
   
   
| 9ms<br>
| 9ms
   
   
| 59.859ms<br>
| 29.295ms
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms<br>
| class="close" | 8ms <ref name="count"/>
 
|}
|}


Zeile 378: Zeile 374:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |
 
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 388: Zeile 384:
|-
|-
! [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
| 8ms / 4ms
| O(1)
| 3ms
| O(1)
| 4ms
| O(n)
| 0ms <ref name="clear"/>
| class="close" | O(1)
| class="close" | 0ms <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)
| 50ms
| O(log n)
| 59ms
| O(log n)
| 30ms
| O(n)
| 0ms <ref name="clear"/>
| class="close" | O(1)
| class="close" | 0ms <ref name="count"/>
|-
|-
! [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
| 24ms / 10ms
| O(1)
| 9ms
| O(1)
| 8ms
| O(n)
| 0ms <ref name="clear"/>
| class="close" | O(1)
| class="close" | 0ms <ref name="count"/>
|-
|-
! [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)
| 3.190ms
| O(n)
| 3.147ms
| O(log n)
| 20ms
| O(n)
| 0ms <ref name="clear"/>
| class="close" | O(1)
| class="close" | 0ms <ref name="count"/>
|}  
|}
 
=== Testobject (reference-Typ) ===
=== Testobject (reference-Typ) ===
==== ein-elementige Datenstrukturen  ====
==== ein-elementige Datenstrukturen  ====
Zeile 424: Zeile 421:
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
   
   
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
Zeile 442: Zeile 439:
! [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;]
   
   
| 10ms / 4ms
| 19ms / 13ms
   
   
| 4ms
| 13ms
   
   
| 48.240ms
| 76.329ms
   
   
| 4ms
| 14ms
   
   
| 0ms
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms
| class="close" | 3ms <ref name="count"/>
|-
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
   
   
| 7ms
| 15ms / 5ms
   
   
| 28.883ms
| 60.987ms
   
   
| 63.349ms
| 83.695ms
   
   
| 58.970ms
| 53.370ms
   
   
| 0ms
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms
| class="close" | 3ms <ref name="count"/>
|-
|-
! [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;]
   
   
| 2ms
| 2ms / 2ms
   
   
| 5848ms
| 42.624ms
   
   
| 2ms
| 3ms
   
   
| 61.034ms
| 52.683ms
   
   
| 0ms
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms
| class="close" | 3ms <ref name="count"/>
|-
|-
! [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;]
   
   
| 2ms /&nbsp;1ms
| 6ms / 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>
| 1ms <ref name="removefirst"/>
   
   
| 76.947ms<br>
| 80.020ms
   
   
| 204.310ms<br>
| 183.873ms
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms<br>
| class="close" | 137.493ms <ref name="countenumerate"/>
|-
|-
! [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;]
   
   
| 1ms <br>
| 2ms
   
   
| 1ms<ref name="removefirst" /><br>
| 1ms<ref name="removefirst" />
   
   
| 53.155ms<br>
| 75.154ms
   
   
| 192.108ms<br>
| 167.390ms
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
   
   
| class="close" | 0ms<br>
| class="close" | 128.508ms <ref name="countenumerate"/>
|-
|-
! [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;]
   
   
| 8ms /&nbsp;7ms<br>
| 9ms / 8ms
   
   
| 101.157ms<br>
| 60.109ms
   
   
| 9ms<br>
| 9ms
   
   
| 59.859ms<br>
| 62.040ms
   
   
| 0ms<br>
| 0ms <ref name="clear"/>
 
| class="close" | 0ms<br>
| class="close" | 9ms <ref name="count"/>
 
|}
|}


Zeile 531: Zeile 529:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |
 
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 541: Zeile 539:
|-
|-
! [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"/>
| class="close" | O(1)
| 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)
| 155ms / 150ms
| O(log n)
| 162ms
| O(log n)
| 139ms
| O(n)
| 0ms <ref name="clear"/>
| class="close" | O(1)
| class="close" | 1ms <ref name="count"/>
|-
|-
! [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"/>
| class="close" | O(1)
| class="close" | 0ms <ref name="count"/>
|-
|-
! [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"/>
| class="close" | O(1)
| class="close" | 1ms <ref name="count"/>
|}
|}


Zeile 576: Zeile 574:


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