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 178: Zeile 178:
=== zwei-elementige Datenstrukturen  ===
=== zwei-elementige Datenstrukturen  ===
Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:  
Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:  
* Keys müssen eindeutig sein.
* Keys müssen eindeutig sein.
* Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
* Keys dürfen nicht von "außen" verändert werden (''immutable''). 
* Die Values können über die [http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx Item-Property] der Datenstruktur angesprochen werden:<br><source lang="csharp">myDataStructure[key] = expression;</source>Dabei wird ein Wert
* Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.  
** wenn der Key bereits vorhanden ist überschrieben
* Die Values können über die [http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx Item-Property] der Datenstruktur angesprochen werden:<br><source lang="csharp">myDataStructure[key] = expression;</source>Dabei wird ein Wert  
** wenn der Key bereits vorhanden ist überschrieben  
** 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).
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.
   
   


{| class="default"
{| class="default"
|-
|-
| class="blank" |
| class="blank" |  
! colspan="6" | Laufzeiten
! colspan="5" | Laufzeiten  
| class="blank" |  
| class="blank" |  
|-
|-
| class="blank" |
| class="blank" |  
! Add  
! Add  
! Remove  
! Remove  
! ElementAt
! ContainsKey
! Contains
! Clear  
! Clear  
! Count  
! Count  
! Element-Typ  
! Element-Typ  
! [[ThreadSafety|Thread-safe]]
! [[ThreadSafety|Thread-safe]]  
! Bemerkungen
! Bemerkungen
|-
|-
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary<TKey, TValue>]
! [http://msdn.microsoft.com/en-us/library/xfhwa508.aspx Dictionary&lt;TKey, TValue&gt;]  
| O(1)<br>O(n) wenn Count + 1 > Capacity
| O(1)<br>O(n) wenn Count + 1 &gt; Capacity  
| O(1)
| O(1)  
|
| O(1)  
| O(1)
| O(n)
|  
| O(1)  
| O(1)
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
|  
| Nein  
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode
| class="close" | Verfügt über [[TryGetValue]]-Methode
|-
|-
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary<TKey, TValue>]
! [http://msdn.microsoft.com/en-us/library/f7fta44c.aspx SortedDictionary&lt;TKey, TValue&gt;]
| O(log n)  
| O(log n)  
| O(log n)  
| O(log n)  
|
| O(log n)  
| O(log n)  
|
| O(n)
|
| O(1)
|
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| Nein  
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten  
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedList bei unsortierten Daten
|-
|-
! [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)
|
| O(1)
| 
| O(n)
|  
| O(1)
|  
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<object,object>]<br>oder<br>[http://msdn.microsoft.com/en-us/library/system.collections.dictionaryentry.aspx DictionaryEntry]
|  
| Read-Only mit einem schreibenden Thread
| Read-Only mit einem schreibenden Thread
| class="close" |  
| class="close" | Die initiale Capacity der Hashtable kann im [[Konstruktor]] angegeben werden: [http://msdn.microsoft.com/en-us/library/k3x9ky40.aspx <tt>Hashtable(Int32)</tt>]
|-
|-
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList<TKey, TValue>]
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
| O(n)  
| O(n)
| O(n)
| O(n)
|
| O(log n)
| O(log n)
|  
| O(n)
|  
| O(1)
|  
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| Nein  
| 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]]


== Referenzen ==
== Referenzen ==

Version vom 19. April 2009, 17:07 Uhr



Hinweise

  • 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.
  • n entspricht immer dem Count der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
  • Mit Element-Typ wird hier der Wert bezeichnet, den der Enumerator bei einer Foreach-Anweisung zurückgibt.
  • ElementAt ist eine spezielle Extension Method. Bei Strukturen die das Interface IList<T> implementieren gibt sie das Element an der angegebenen Position an, ansonsten iteriert sie so oft wie angegeben und gibt das Element an dieser Stelle zurück. [1]
  • 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)

ein-elementige Datenstrukturen


 Laufzeiten

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

Remove und Add sind Deqeue und Enqueue


Stack<T> O(1)
O(n) wenn Count + 1 > Capacity
O(1)
 O(n)
 O(n)
 O(n)
 O(1)
 T
 Nein
 Remove und Add sind Pop und Push
SynchronizedCollection<T> O(1)
O(n) wenn Count + 1 > Capacity
 O(n)
 O(1)
 O(n)
 O(n)
 O(1)
 T
 Ja

benutzt intern List<T>, hat aber zusätzliche Mechanismen
um Thread-safety zu garantieren


zwei-elementige Datenstrukturen

Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:

  • Keys müssen eindeutig sein.
  • Keys dürfen nicht von "außen" verändert werden (immutable).
  • Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
  • Die Values können über die Item-Property der Datenstruktur angesprochen werden:
    myDataStructure[key] = expression;
    Dabei wird ein Wert
    • wenn der Key bereits vorhanden ist überschrieben
    • wenn der Key noch nicht vorhanden ist neu angelegt.
  • Sie implementieren das IDictionary-Interface.
  • Die Laufzeit für ElementAt ist O(n).

Außerdem sortieren sowohl SortedDictionary<TKey,TValue> als auch SortedList<TKey,TValue> 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 TKey, der das Interface IComparer<T> erfüllt.


Laufzeiten
Add Remove ContainsKey Clear Count Element-Typ Thread-safe Bemerkungen
Dictionary<TKey, TValue> O(1)
O(n) wenn Count + 1 > Capacity 		O(1) O(1) O(n) O(1) KeyValuePair<TKey,TValue> Nein Verfügt über TryGetValue-Methode
SortedDictionary<TKey, TValue> O(log n) O(log n) O(log n) O(n) O(1) KeyValuePair<TKey,TValue> Nein Verfügt über TryGetValue-Methode
schneller als SortedList bei unsortierten Daten
Hashtable O(1)
O(n) wenn Count + 1 > Capacity 		O(1) O(1) O(n) O(1) KeyValuePair<object,object>
oder
DictionaryEntry 		Read-Only mit einem schreibenden Thread Die initiale Capacity der Hashtable kann im Konstruktor angegeben werden: Hashtable(Int32)
SortedList<TKey, TValue> O(n) O(n) O(log n) O(n) O(1) KeyValuePair<TKey,TValue> Nein Verfügt über TryGetValue-Methode
schneller als SortedDictionary bei vorsortierten Daten

Referenzen

  1. ↑ Enumerable.ElementAt<TSource> Method
Abgerufen von „https://sopranium.de/index.php?title=Datenstrukturen&oldid=467“