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 248: Zeile 248:


== Laufzeiten nach eigenen Tests in ms ==
== Laufzeiten nach eigenen Tests in ms ==
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.
Der Quellcode des für die Tests verwendeten Miniprogramms kann [[DatenstrukturenSpeedTest|hier]] eingesehen werden.


Zeile 271: Zeile 273:
! Clear
! Clear
   
   
! Count
! Count  
 
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
|-
|-
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>]
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>]
Zeile 291: Zeile 288:
| O(n)
| O(n)
   
   
| O(1)
| class="close" | 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;]
Zeile 311: Zeile 303:
| O(n)
| O(n)
   
   
| O(1)
| class="close" | O(1)
   
   
| T
| Nein
| class="close" |
|-
|-
! [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;]
Zeile 331: Zeile 318:
| O(n)
| O(n)
   
   
| O(1)
| class="close" | O(1)
 
| T
| Nein
| class="close" |  
|-
|-
! [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;]
Zeile 351: Zeile 333:
| O(n)<br>
| O(n)<br>
   
   
| O(1)<br>
| class="close" | O(1)<br>
| T<br>
| Nein<br>
| class="close" |
Remove und Add sind Deqeue und Enqueue


|-
|-
Zeile 374: Zeile 348:
| O(n)<br>
| O(n)<br>
   
   
| O(1)<br>
| class="close" | O(1)<br>  
 
| T<br>
| Nein<br>
| class="close" | Remove und Add sind Pop und Push<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;]
Zeile 394: Zeile 363:
| O(n)<br>
| O(n)<br>
   
   
| O(1)<br>
| class="close" | O(1)<br>
| T<br>
| Ja<br>
| class="close" |  
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen<br>um [[ThreadSafety|Thread-safety]] zu garantieren


|}
|}
Zeile 420: Zeile 381:
! Clear  
! Clear  
! Count  
! Count  
! Element-Typ
! [[ThreadSafety|Thread-safe]]
! Bemerkungen
|-
|-
! [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;]  
Zeile 429: Zeile 387:
| O(1)  
| O(1)  
| O(n)  
| O(n)  
| O(1)
| class="close" | O(1)
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode
|-
|-
! [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;]
Zeile 439: Zeile 394:
| O(log n)  
| O(log n)  
| O(n)  
| O(n)  
| O(1)
| class="close" | O(1)
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| 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]  
Zeile 449: Zeile 401:
| O(1)
| O(1)
| O(n)  
| O(n)  
| O(1)
| class="close" | 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
| 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&lt;TKey, TValue&gt;]
! [http://msdn.microsoft.com/en-us/library/ms132319.aspx SortedList&lt;TKey, TValue&gt;]
Zeile 459: Zeile 408:
| O(log n)
| O(log n)
| O(n)
| O(n)
| O(1)
| class="close" | O(1)
| [http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx KeyValuePair<TKey,TValue>]
| Nein
| class="close" | Verfügt über [[TryGetValue]]-Methode<br>schneller als SortedDictionary bei vorsortierten Daten
|} [[Kategorie:Code-Beispiele]]
|} [[Kategorie:Code-Beispiele]]


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