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
Dietsch (Diskussion | Beiträge)
Bürokraten, sopra, sopra17, sopradozenten, soprapre17, Administratoren
2.877 Bearbeitungen
Keine Bearbeitungszusammenfassung
Zeile 2: Zeile 2:


== Hinweise  ==
== Hinweise  ==
* Falls nicht anders angegeben sind Laufzeiten immer Average Case. 
* Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung]. 
* Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|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 [http://msdn.microsoft.com/en-us/library/bb383977.aspx Extension Method]. Bei Strukturen die das Interface [http://msdn.microsoft.com/en-us/library/5y536ey6.aspx 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. <ref>[http://msdn.microsoft.com/en-us/library/bb299233.aspx Enumerable.ElementAt<TSource> Method]</ref>
* 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 [http://msdn.microsoft.com/en-us/ MSDN]) ==
*Falls nicht anders angegeben sind Laufzeiten immer Average Case.
*Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung].
*Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|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 [http://msdn.microsoft.com/en-us/library/bb383977.aspx Extension Method]. Bei Strukturen die das Interface [http://msdn.microsoft.com/en-us/library/5y536ey6.aspx IList&lt;T&gt;] 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. <ref>[http://msdn.microsoft.com/en-us/library/bb299233.aspx Enumerable.ElementAt&lt;TSource&gt; Method]</ref>
*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 [http://msdn.microsoft.com/en-us/ MSDN]) ==
 
=== ein-elementige Datenstrukturen  ===
=== ein-elementige Datenstrukturen  ===


Zeile 121: Zeile 129:
| class="close" |  
| class="close" |  
Remove und Add sind Deqeue und Enqueue  
Remove und Add sind Deqeue und Enqueue  


|-
|-
Zeile 163: Zeile 172:
| class="close" |  
| class="close" |  
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen<br>um [[ThreadSafety|Thread-safety]] zu garantieren
benutzt intern List&lt;T&gt;, hat aber zusätzliche Mechanismen<br>um [[ThreadSafety|Thread-safety]] zu garantieren
|}
|}


<h3> zwei-elementige Datenstrukturen  </h3>
=== zwei-elementige Datenstrukturen  ===
<p>Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:  
Alle Datenstrukturen in dieser Liste haben folgendes gemeinsam:  
</p><p><br />
</p>
* Keys müssen eindeutig sein.
<ul><li>Keys müssen eindeutig sein.  
* Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
</li></ul>
* 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
<ul><li>Die Add-Methode wirft eine Exception wenn der Key bereits vorhanden ist.
** wenn der Key bereits vorhanden ist überschrieben
</li></ul>
** wenn der Key noch nicht vorhanden ist neu angelegt.
<ul><li>Die Values können über die <a href="http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx">Item-Property</a> der Datenstruktur angesprochen werden:<br /><span class="fck_mw_source" _fck_mw_customtag="true" _fck_mw_tagname="source" lang="csharp">myDataStructure[key] = expression;</span>Dabei wird ein Wert  
* Sie implementieren das [http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx IDictionary]-Interface.
</li></ul>
<ul><li><ul><li>wenn der Key bereits vorhanden ist überschrieben
</li></ul>
</li></ul>
<ul><li><ul><li>wenn der Key noch nicht vorhanden ist neu angelegt.
</li></ul>
</li></ul>
<ul><li>Sie implementieren das <a href="http://msdn.microsoft.com/en-us/library/system.collections.idictionary.aspx">IDictionary</a>-Interface.
</li></ul>
<p><br />
</p><p><br />
</p>
<table class="default">


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


== Referenzen ==
== Referenzen ==
<references/>
<references />
 


[[Category:CSharp]]
[[Category:CSharp]] [[Kategorie:Code-Beispiele]]
Abgerufen von „https://sopranium.de/Datenstrukturen“