Oft stellt man sich die Frage, welche Datenstruktur nutze ich eigentlich für meinen Algorithmus. Die falsche Entscheidung kann zu erheblichen Performanceeinbußen kommen. Dieser Artikel soll Ihnen die Erkenntnisse liefern, die Sie benötigen, um fundierte Entscheidungen zu treffen.
List
Stellt euch ein Schweizer Taschenmesser vor. Vielseitig, oder? Das ist unsere Liste! Es ist das Werkzeug der Wahl, wenn Du ein bisschen von allem brauchst.
Wofür ist diese gut?
- Speicherung von Elementen in einer spezifischen Reihenfolgen.
- Hinzufügen und Löschen von Elementen an einer beliebigen Position.
- Zugriff auf Elemente über ihren Index.
Hier ein Codebeispiel:
Unter der Haube verwendet List ein dynamisches Array. Er ist wie ein magischer, erweiterbarer Koffer – er wächst, wenn du weitere Gegenstände hinzufügst. Aber hier ist der Clou!
Wenn es wächst, fügt es nicht nur einen weiteren Platz hinzu. Es verdoppelt die Größe!
Das bedeutet, dass das Hinzufügen von Artikeln in der Regel superschnell geht (O(1)), aber manchmal, wenn es wachsen muss, dauert es etwas länger (O(n)). Im Durchschnitt ist es aber immer noch ziemlich spritzig!
Also, wann sollte man List
Wenn du die Ordnung aufrechterhalten musst.
Wenn du häufig auf Elemente anhand ihrer Position zugreifen möchtest.
Wenn du es mit einer Sammlung zu tun hast, deren Größe sich häufig ändert.
und:
Wann sollte man es sich zweimal überlegen?
Wenn du ständig nach Elementen anhand ihres Werts (nicht des Index) suchst.
Wenn Du es mit Millionen von Artikeln zu tun hast und blitzschnelle Nachschlagevorgänge benötigst!!
Dictionary
Wenn ein schneller schlüsselbasierter Abruf Priorität hat, erweist sich Dictionary
Musst du etwas finden? Zapp! du bist sofort da.
Wofür ist es gut?
Blitzschnelle Suche nach Schlüsseln.
Speichern von Schlüssel-Wert-Paaren.
Überprüfen, ob ein Schlüssel vorhanden ist, ohne alles zu durchlaufen.
Code-Beispiel:
Dictionary
Ermöglichung der O(1)-Komplexität der durchschnittlichen Fallzeit für schlüsselbasierte Operationen.
Also, wann sollte man das Wörterbuch verwenden?
Wenn Du blitzschnelle Lookups benötigst.
Wenn Du mit Schlüssel-Wert-Paaren arbeiten musst.
Wenn Du schnell nach Existenz suchen musst.
Zweimal überlegen:
Wenn Du eine bestimmte Reihenfolge beibehalten musst (verwendet stattdessen SortedDictionary
Wenn Du es mit einer kleinen Anzahl von Artikeln zu tun hast(der Aufwand lohnt sich möglicherweise nicht).
HashSet
Stellt euch einen Nachtclub vor, in dem jeder Mensch einzigartig sein muss. Das ist HashSet.
Es ist der Türsteher, der dafür sorgt, dass keine Duplikate eindringen.
Verwendung:
Speichern einer Sammlung einzigartiger Gegenstände.
Superschnelle Überprüfung der Mitgliedschaft.
Festlegen von Operationen wie Vereinigung, Schnittmenge und Differenz.
Code:
HashSet basiert auf dem gleichen Prinzip wie Dictionary
Also, Wann sollte man das Hashset verwenden?
Wenn du die Einzigartigkeit sicherstellen musst.
Wenn du schnelle Mitgliedschaftstests benötigst.
Wenn du Set-Vorgänge ausführen möchtest
und, Wann man es sich zweimal überlegen sollte
Wenn du ihren Elementen Werte zuordnen musst(verwenden Sie Dictionary
Wenn es auf die Reihenfolge ankommt (SortedSet in Betracht ziehen)
Kleine Performance Analyse:
Code:
Ergebnis:
Für Lookup-Operationen zeigen Dictionary
Bei Einfügeoperationen zeigen alle drei Strukturen eine vergleichbare Leistung für einzelne Einfügungen. Bei List
For Memory Utilization List