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
 
(30 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 185: Zeile 182:
** wenn der Key noch nicht vorhanden ist neu angelegt.
** 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.
* Sie implementieren das [http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx IDictionary]-Interface.
* Die Laufzeit für <tt>ElementAt</tt> ist O(n).  
* 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.
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.
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 246: Zeile 243:
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten
|} [[Kategorie:Code-Beispiele]]
|} [[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"
|-
| class="blank" | <br>
! colspan="6" | Laufzeiten
|-
| class="blank" | <br>
! Add
! Remove
! ElementAt
! Contains
! 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="blank" | <br>
! colspan="6" | Laufzeiten
|-
| class="blank" | <br>
! Add
! Remove
! ElementAt
! Contains
! Clear
! Count
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
| 19ms / 13ms
| 13ms
| 76.329ms
| 14ms
| 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;]
| 155ms / 150ms
| 162ms
| 139ms
| 0ms <ref name="clear"/>
| class="close" | 1ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
| 25ms
| 14ms
| 13ms
| 0ms <ref name="clear"/>
| class="close" | 0ms <ref name="count"/>
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| 8.891ms
| 9.025ms
| 117ms
| 0ms <ref name="clear"/>
| class="close" | 1ms <ref name="count"/>
|}
[[Kategorie:Code-Beispiele]]


== Referenzen ==
== Referenzen ==
Zeile 252: Zeile 574:


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