Es wird viel über Datenstrukturen gesprochen, aber ich kann keine einfache Liste von Datenstrukturen und deren praktischer Verwendung finden. Ich versuche für ein Interview zu lernen und ich denke, das würde mir helfen, zusammen mit vielen anderen. Ich suche so etwas:
Datenstruktur - Beispiel / Verwendet für
Hash-Tabelle - schnelle Daten-Suche ... dann geben Sie ein Beispiel
Array - ...
Binärer Baum - ...
Wenn es irgendwo eine solche Ressource gibt, lassen Sie es mich bitte wissen.
Vielen Dank!
EDIT: Ich meine, Wikipedia ist gut und alles, aber auf den meisten Seiten werden praktische Verwendungen nicht aufgeführt. Ich suche etwas mehr als das.
data-structures
Joel
quelle
quelle
Ich bin im selben Boot wie Sie. Ich muss für technische Interviews lernen, aber das Auswendiglernen einer Liste ist nicht wirklich hilfreich. Wenn Sie 3-4 Stunden Zeit haben und einen tieferen Tauchgang machen möchten, empfehle ich das Auschecken
mycodeschool
Ich habe mir Coursera und andere Ressourcen wie Blogs und Lehrbücher angesehen, aber ich finde sie entweder nicht umfassend genug oder am anderen Ende des Spektrums, zu dicht mit den erforderlichen Terminologien der Informatik.
Der Typ im Video hat eine Reihe von Vorträgen über Datenstrukturen. Kümmere dich nicht um die albernen Zeichnungen oder den leichten Akzent. Sie müssen nicht nur verstehen, welche Datenstruktur ausgewählt werden soll, sondern auch einige andere Punkte, die zu berücksichtigen sind, wenn Menschen über Datenstrukturen nachdenken:
Ich habe auch Notizen auf Github gepostet, wenn Sie interessiert sind.
quelle
Nach meinem Verständnis handelt es sich bei der Datenstruktur um alle Daten, die sich im Speicher eines elektronischen Systems befinden und effizient verwaltet werden können. Oft ist es ein Gedächtnisspiel oder eine schnellere Zugänglichkeit von Daten. Auch in Bezug auf den Arbeitsspeicher gibt es Kompromisse bei der Verwaltung von Daten auf der Grundlage der Kosten für das Unternehmen dieses Endprodukts. Effizient verwaltet zeigt uns, wie am besten auf die Daten zugegriffen werden kann, basierend auf den Hauptanforderungen des Endprodukts. Dies ist eine Erklärung auf sehr hoher Ebene, aber Datenstrukturen sind ein großes Thema. Die meisten Interviewer tauchen in Datenstrukturen ein, die sie sich leisten können, um sie je nach Zeit in den Interviews zu diskutieren. Dabei handelt es sich um verknüpfte Listen und verwandte Themen.
Diese Datentypen können nun basierend auf der Art und Weise, wie sie logisch aufgebaut sind und auf sie zugegriffen wird, in primitive, abstrakte und zusammengesetzte Datentypen unterteilt werden.
Ich hoffe, das hilft dir beim Eintauchen.
quelle
Das ausgezeichnete Buch " Algorithm Design Manual" von Skienna enthält ein riesiges Repository an Algorithmen und Datenstrukturen.
Für Tonnen von Problemen werden Datenstrukturen und Algorithmen beschrieben, verglichen und die praktische Verwendung diskutiert. Der Autor verweist auch auf Implementierungen und die Originalarbeiten.
Das Buch ist großartig, wenn Sie die beste Datenstruktur für Ihr zu lösendes Problem suchen. Es ist auch sehr hilfreich für die Vorbereitung von Interviews.
Eine weitere großartige Ressource ist das NIST Dictionary of Data Strukturen und Algorithmen .
quelle
Nur wenige weitere praktische Anwendung von Datenstrukturen
Rot-Schwarz-Bäume (Wird bei häufigem Einfügen / Löschen und wenigen Suchvorgängen verwendet) - K-Mittelwert-Clustering mit rotem Schwarzbaum, Datenbanken, einfältiger Datenbank, Suchen von Wörtern in Wörterbüchern, Suchen im Web
AVL-Bäume (mehr Suche und weniger Einfügen / Löschen) - Datenanalyse und Data Mining sowie die Anwendungen, bei denen mehr gesucht wird
Min Heap - Clustering-Algorithmen
quelle
Jedes Ranking verschiedener Datenstrukturen ist zumindest teilweise an den Problemkontext gebunden. Es wäre hilfreich zu lernen, wie man die zeitliche und räumliche Leistung von Algorithmen analysiert. Typischerweise wird die "große O-Notation" verwendet, z. B. erfolgt die binäre Suche in der Zeit O (log n), was bedeutet, dass die Zeit für die Suche nach einem Element das Protokoll (implizit in Basis 2) der Anzahl der Elemente ist. Intuitiv erhöht die Verdoppelung der Anzahl der Elemente die Zeit um 1 Schritt, da bei jedem Schritt die Hälfte der verbleibenden Daten als irrelevant verworfen wird. (Die binäre Suche lässt sich recht gut skalieren.) Die Speicherleistung betrifft, wie der Speicher für größere Datenmengen wächst. Beachten Sie außerdem, dass die Big-O-Notation konstante Faktoren ignoriert. Bei kleineren Datensätzen ist ein O (n ^ 2) -Algorithmus möglicherweise immer noch schneller als ein O (n * log n) -Algorithmus mit einem höheren konstanten Faktor.
Neben Zeit und Raum gehören zu den weiteren Merkmalen, ob eine Datenstruktur sortiert ist (Bäume und Skiplisten werden sortiert, Hash-Tabellen nicht), Persistenz (Binärbäume können Zeiger aus älteren Versionen wiederverwenden, während Hash-Tabellen an Ort und Stelle geändert werden) usw.
Während Sie das Verhalten mehrerer Datenstrukturen lernen müssen, um sie vergleichen zu können, besteht eine Möglichkeit, ein Gefühl dafür zu entwickeln, warum sie sich in der Leistung unterscheiden, darin, einige genau zu untersuchen. Ich würde vorschlagen, einfach verknüpfte Listen, binäre Suchbäume und Sprunglisten zu vergleichen , die alle relativ einfach sind, aber sehr unterschiedliche Eigenschaften haben. Überlegen Sie, wie viel Arbeit erforderlich ist, um einen Wert zu finden, einen neuen Wert hinzuzufügen, alle Werte in der richtigen Reihenfolge zu finden usw.
Es gibt verschiedene Texte zur Analyse der Leistung von Algorithmen / Datenstrukturen, die von den Leuten empfohlen werden, aber was sie für mich wirklich sinnvoll machte, war das Erlernen von OCaml. Der Umgang mit komplexen Datenstrukturen ist die Stärke von ML, und ihr Verhalten ist viel klarer, wenn Sie Zeiger und Speicherverwaltung wie in C vermeiden können. (OCaml nur zu lernen, um Datenstrukturen zu verstehen, ist jedoch mit ziemlicher Sicherheit der lange Weg. :))
quelle