Datenstrukturen: Unterschied zwischen den Versionen

Aus Das Sopra Wiki
Zur Navigation springen Zur Suche springen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Zeile 14: Zeile 14:
{| class="default"
{| class="default"
|-
|-
| class="blank" | <br>  
| class="blank" | <br>
! colspan="6" | Laufzeiten von Methoden  
! colspan="6" | Laufzeiten von Methoden
| class="blank" | <br>
| class="blank" | <br>
|-
|-
| class="blank" | <br>  
| class="blank" | <br>
! Add  
! Remove  
! Add
! ElementAt  
! Contains  
! Remove
! Clear  
! Count  
! ElementAt
! Element-Typ  
! [[ThreadSafety|Thread-safe]]  
! Contains
! Clear
! Count
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
! Bemerkungen
|-
|-
! [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)  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity
| &nbsp;?  
| O(1)  
| O(1)
| O(n)  
| O(1)  
| &nbsp;?
| T  
| Nein  
| O(1)
| class="close" | keine Duplikate<br>keine Ordnung
| O(n)
| O(1)
| T
| Nein
| class="close" | keine Duplikate<br>
|-
|-
! [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;]
| O(1)<br>  
| O(1)<br>  
| O(1)<br>
| O(n)<br>  
| O(n)<br>  
| O(1)<br>
| O(1)<br>  
| O(1)<br>  
| O(n)<br>
| T<br>  
| Nein<br>  
| O(n)<br>
| class="close" | Ordnung<br>Duplikate<br>
| O(1)<br>
| O(1)<br>
| T<br>
| Nein<br>
| class="close" | <br>
|-
|-
! [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<br>  
| O(n)<br>  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| O(1)<br>  
| O(n)<br>  
| O(n)<br>
| <br>  
| O(1)<br>  
| O(1)<br>
| T<br>  
| Nein<br>  
| O(n)<br>
| <br>
| O(1)<br>
| T<br>
| Nein<br>
| class="close" | <br>
| class="close" | <br>
|-
|-
! [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<br>  
| <br>  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| <br>  
| <br>  
| <br>
| <br>  
| <br>  
| <br>
| T<br>  
| Nein<br>  
| <br>
| <br>
| <br>
| T<br>
| Nein<br>
| class="close" | <br>
| class="close" | <br>
|-
|-
! [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(1)<br>O(n) wenn Count + 1 &gt; Capacity <br>
| <br>  
| <br>  
| O(1)<br>
| <br>  
| <br>  
| <br>
| T<br>  
| Nein<br>  
| <br>
| <br>
| <br>
| T<br>
| Nein<br>
| class="close" | <br>
| class="close" | <br>
|-
|-
! [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(n)<br>  
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity<br>
| O(1)<br>  
| O(n)<br>  
| O(n)<br>
| <br>  
| O(1)<br>  
| O(1)<br>
| T<br>  
| Ja<br>  
| O(n)<br>
| class="close" | benutzt intern List&lt;T&gt;<br>
| <br>
| O(1)<br>
| T<br>
| Ja<br>
| class="close" |  
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen
 
um Thread-Safety zu garantieren<br>
 
|}
|}


Version vom 19. April 2009, 12:18 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 (alle außer Hashtable) 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.
  • Datenstrukturen die auf Arrays basieren besitzen intern eine Capacity. Diese gibt die aktuelle Größe des internen Arrays an. Capacity ist immer größer bzw. gleich Count. Sollte beim Hinzufügen eines Elements die Capacity der Struktur überschritten werden, muss diese wachsen. Dazu erzeugt sie intern einen neuen, größeren Array und kopiert alle bis dahin vorhandenen Einträge in diesen neuen Array. Typischerweise ist die neue Größe des Arrays die erste Primzahl, die größer als das Doppelte der alten Capacity ist.

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
LinkedList<T> O(1)
 O(1)
 O(n)
 O(n)
 O(1)
 O(1)
 T
 Nein
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>, hat aber zusätzliche Mechanismen

um Thread-Safety zu garantieren

...


 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=421“