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
 
(12 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>
Zeile 191: Zeile 191:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |  
| colspan="3" class="blank" | <br>
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 247: 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 268: Zeile 268:
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
   
   
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
Zeile 374: Zeile 374:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |
 
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 421: Zeile 421:
! colspan="6" | Laufzeiten
! colspan="6" | Laufzeiten
   
   
| class="blank" | <br>
 
|-
|-
| class="blank" | <br>
| class="blank" | <br>
Zeile 439: 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 528: Zeile 529:
| class="blank" |  
| class="blank" |  
! colspan="5" | Laufzeiten  
! colspan="5" | Laufzeiten  
| class="blank" |
 
|-
|-
| class="blank" |  
| class="blank" |  
Zeile 538: 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 573: Zeile 574:


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