Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
VisuellWikitext
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Keine Bearbeitungszusammenfassung
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Zeile 253: Zeile 253:


Die Tests wurden mit folgenden Parametern durchgeführt:  
Die Tests wurden mit folgenden Parametern durchgeführt:  
* Alle Messungen wurden mit <tt>System.Diagnostics.Stopwatch</tt> durchgeführt.
* erster Test: Elemente vom Typ Int32
* Es wurden 100.000 zufällige und disjunkte Int32 Werte erzeugt (zwischen 0 und Int32.Max) und in einem Array gespeichert.
** Alle Messungen wurden mit <tt>System.Diagnostics.Stopwatch</tt> durchgeführt.
* Diese Werte wurden für die Tests Add (mit [[foreach]]), Remove (mit [[for]]), ElementAt (mit [[for]]) und Contains (mit [[for]]) aus diesem Array extrahiert.  
** 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.
* zweiter Test: 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 Tests Add (mit [[foreach]]), Remove (mit [[for]]), ElementAt (mit [[for]]) und Contains (mit [[for]]) aus diesem Array extrahiert.


=== ein-elementige Datenstrukturen  ===
=== Int32 (value-type) ===
==== ein-elementige Datenstrukturen  ====


{| class="default"
{| class="default"
Zeile 366: Zeile 372:
|}
|}


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


{| class="default"
{| class="default"
Zeile 408: Zeile 414:
| O(n)
| O(n)
| class="close" | O(1)
| class="close" | O(1)
|} [[Kategorie:Code-Beispiele]]
|}  
=== Testobject (reference-Typ) ===
==== ein-elementige Datenstrukturen  ====
 
{| class="default"
|-
| class="blank" | <br>
! colspan="6" | Laufzeiten
| class="blank" | <br>
|-
| class="blank" | <br>
! Add
! Remove
! ElementAt
! Contains
! Clear
! Count
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet&lt;T&gt;]
| 10ms / 4ms
| 4ms
| 48.240ms
| 4ms
| 0ms
| class="close" | 0ms
|-
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList&lt;T&gt;]
| 7ms
| 28.883ms
| 63.349ms
| 58.970ms
| 0ms
| class="close" | 0ms
|-
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List&lt;T&gt;]
| 2ms
| 5848ms
| 2ms
| 61.034ms
| 0ms
| class="close" | 0ms
|-
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue&lt;T&gt;]
| 2ms /&nbsp;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>
| 76.947ms<br>
| 204.310ms<br>
| 0ms<br>
| class="close" | 0ms<br>
|-
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack&lt;T&gt;]
| 1ms <br>
| 1ms<ref name="removefirst" /><br>
| 53.155ms<br>
| 192.108ms<br>
| 0ms<br>
| class="close" | 0ms<br>
|-
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection&lt;T&gt;]
| 8ms /&nbsp;7ms<br>
| 101.157ms<br>
| 9ms<br>
| 59.859ms<br>
| 0ms<br>
| class="close" | 0ms<br>
|}
 
==== zwei-elementige Datenstrukturen  ====
 
{| class="default"
|-
| class="blank" |
! colspan="5" | Laufzeiten
| class="blank" |
|-
| class="blank" |
! Add
! Remove
! ContainsKey
! Clear
! Count
|-
! [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)
| O(1)
| O(n)
| class="close" | O(1)
|-
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| O(log n)
| O(log n)
| O(log n)
| O(n)
| class="close" | O(1)
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
| O(1)<br>O(n) wenn Count + 1 > Capacity
| O(1)
| O(1)
| O(n)
| class="close" | O(1)
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| O(n)
| O(n)
| O(log n)
| O(n)
| class="close" | O(1)
|}
 
[[Kategorie:Code-Beispiele]]


== Referenzen ==
== Referenzen ==
Abgerufen von „https://sopranium.de/Datenstrukturen“