Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
← Zum vorherigen VersionsunterschiedZum nächsten Versionsunterschied →
VisuellWikitext
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Zeile 95: Zeile 95:
|}
|}


=== ... ===
=== ... ===
<table class="default">
<tr><td class="blank"></td><th colspan="6">Laufzeiten von Methoden</th><td class="blank"></td></tr>
<tr><td class="blank"></td><th>Add</th><th>Remove</th><th>ElementAt</th><th>Contains</th><th>Clear</th><th>Count</th><th>Element-Typ</th><th>[[ThreadSafety|Thread-safe]]</th><th>Bemerkungen</th></tr>
<tr><th>[http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary<TKey, TValue>]</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td class="close"></td></tr>
<tr><th>[http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary<TKey, TValue>]</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td class="close"></td></tr>
<tr><th>[http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td class="close"></td></tr>
<tr><th>[http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList<TKey, TValue>]</th><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td class="close"></td></tr>
</table>


[[Kategorie:CSharp]]
{| class="default"
|-
| class="blank" | <br>
! colspan="6" | Laufzeiten von Methoden
| class="blank" | <br>
|-
| class="blank" | <br>
! Add
! Remove
! ElementAt
! Contains
! Clear
! Count
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| O(1)<br>
| <br>
| O(1)<br>
| <br>
| <br>
| <br>
| Nein<br>
| class="close" | <br>
|-
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| O(log n)<br>
| O(log n)<br>
| <br>
| O(log n)<br>
| <br>
| <br>
| <br>
| Nein<br>
| class="close" | schneller als SortedList bei unsortierten Daten<br>
|-
! [http://msdn.microsoft.com/en-us/library/system.collections.hashtable.aspx Hashtable]
| <br>
| <br>
| <br>
| <br>
| <br>
| <br>
| <br>
| Read-Only mit einem schreibenden Thread<br>
| class="close" | <br>
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| O(n)<br>
| O(n)<br>
| <br>
| O(log n)<br>
| <br>
| <br>
| <br>
| Nein<br>
| class="close" | schneller als SortedDictionary bei vorsortierten Daten<br>
|}
 
[[Category:CSharp]]

Version vom 18. April 2009, 23:44 Uhr



Hinweise

  • n entspricht immer dem Count der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
  • Falls nicht anders angegeben sind Laufzeiten immer Average Case.
  • Alle Links zu den Datenstrukturen zeigen auf die englische Version der MSDN. Diese ist typischerweise vollständiger und genauer als ihre deutsche Übersetzung.
  • Die meisten der hier vorgestellten Datenstrukturen sind Generics. Ihre Verwendung wird im Generic-Artikel erklärt.
  • Mit Element-Typ wird hier der Wert bezeichnet, den der Enumerator bei einer foreach-Anweisung zurückgibt.

Laufzeiten und Eigenschaften (nach MSDN)

...


 Laufzeiten von Methoden

Add Remove ElementAt Contains Clear Count Element-Typ Thread-safe Bemerkungen
HashSet<T> O(1)
O(n) wenn Count + 1 > Capacity 		O(1)  ? O(1) O(n) O(1) T Nein keine Duplikate
keine Ordnung
LinkedList<T> O(1)
 O(1)
 O(n)
 O(n)
 O(1)
 O(1)
 T
 Nein
 Ordnung
Duplikate
List<T> O(1)
O(n) wenn Count + 1 > Capacity
 O(n)
 O(1)
 O(n)
O(1)
 T
 Nein
Queue<T> O(1)
O(n) wenn Count + 1 > Capacity




T
 Nein
Stack<T> O(1)
O(n) wenn Count + 1 > Capacity
O(1)



T
 Nein
SynchronizedCollection<T> O(1)
O(n) wenn Count + 1 > Capacity
 O(n)
 O(1)
 O(n)
O(1)
 T
 Ja
 benutzt intern List<T>

...


 Laufzeiten von Methoden

Add Remove ElementAt Contains Clear Count Element-Typ Thread-safe Bemerkungen
Dictionary<TKey, TValue> O(1)
O(n) wenn Count + 1 > Capacity
 O(1)
O(1)


Nein
SortedDictionary<TKey, TValue> O(log n)
 O(log n)
O(log n)


Nein
 schneller als SortedList bei unsortierten Daten
Hashtable






Read-Only mit einem schreibenden Thread
SortedList<TKey, TValue> O(n)
 O(n)
O(log n)


Nein
 schneller als SortedDictionary bei vorsortierten Daten
Abgerufen von „https://sopranium.de/index.php?title=Datenstrukturen&oldid=384“