Frage Was sind die weniger bekannten, aber nützlichen Datenstrukturen?


Es gibt einige Datenstrukturen, die wirklich nützlich sind, aber den meisten Programmierern unbekannt sind. Welche sind sie?

Jeder weiß über verknüpfte Listen, Binärbäume und Hashes Bescheid, aber was ist mit Listen überspringen und Bloom-Filter beispielsweise. Ich würde gerne mehr Datenstrukturen kennen, die nicht so gebräuchlich sind, aber wissenswert sind, weil sie sich auf großartige Ideen stützen und die Toolbox eines Programmierers bereichern.

PS: Mich interessieren auch Techniken wie Tanzende Verbindungen welche die Eigenschaften einer gemeinsamen Datenstruktur geschickt nutzen.

BEARBEITEN: Bitte versuche zu Fügen Sie Links hinzu auf Seiten, die die Datenstrukturen detaillierter beschreiben. Versuchen Sie außerdem, ein paar Wörter hinzuzufügen Warum eine Datenstruktur ist cool (wie Jonas Kölker bereits darauf hingewiesen). Versuchen Sie auch, zu liefern eine Datenstruktur pro Antwort. Dadurch können die besseren Datenstrukturen allein aufgrund ihrer Abstimmungen an die Spitze gelangen.


797


Ursprung


Antworten:


Versucht, auch bekannt als Präfix-Bäume oder kritische Bit-Bäume, existieren seit über 40 Jahren, sind aber immer noch relativ unbekannt. Eine sehr coole Verwendung von Versuchen wird beschrieben inTRASH - Eine dynamische LC-Trie und Hash-Datenstruktur", die einen Trie mit einer Hash-Funktion kombiniert.


271



Bloom-Filter: Bit-Array von m Bits, anfangs alle auf 0 gesetzt.

Um ein Element hinzuzufügen, führst du es durch k Hash-Funktionen, die Ihnen geben k Indizes im Array, die Sie dann auf 1 setzen.

Um zu prüfen, ob ein Element in der Menge enthalten ist, berechnen Sie die k Indizes und prüfen, ob sie alle auf 1 gesetzt sind.

Natürlich ergibt dies eine gewisse Wahrscheinlichkeit von falsch-positiven Ergebnissen (laut Wikipedia ist es etwa 0,61 ^ (m / n), wobei n die Anzahl der eingefügten Elemente ist). Falsch-Negative sind nicht möglich.

Das Entfernen eines Elements ist unmöglich, aber Sie können es implementieren Zählen Bloom Filter, dargestellt durch ein Array von Ints und Inkrement / Dekrement.


231



Seil: Es ist eine Zeichenfolge, die billige Prepends, Substrings, Middle-Insertionen und Anhängen ermöglicht. Ich habe wirklich nur einmal dafür gebraucht, aber keine andere Struktur hätte ausgereicht. Regelmäßige Strings und Arrays Prepends waren einfach viel zu teuer für das, was wir tun mussten, und alles umzukehren kam nicht in Frage.


140



Listen überspringen sind ziemlich ordentlich.

Wikipedia
  Eine Skip-Liste ist eine probabilistische Datenstruktur, die auf mehreren parallelen, sortierten verknüpften Listen basiert, deren Effizienz mit einem binären Suchbaum vergleichbar ist (Auftragsprotokoll n durchschnittliche Zeit für die meisten Operationen).

Sie können als Alternative zu ausgewogenen Bäumen verwendet werden (anstelle einer strengen Durchsetzung des Ausgleichs). Sie sind einfach zu implementieren und schneller als ein rot-schwarzer Baum. Ich denke, dass sie in jeder guten Programmierer-Toolbox sein sollten.

Wenn Sie eine detaillierte Einführung in Skip-Listen erhalten möchten, hier ist ein Link zu einem Video von MIT Einführung in Algorithmen Vorlesung über sie.

Ebenfalls, Hier ist ein Java-Applet, das Skip-Listen visuell demonstriert.


128



Räumliche Indizes, bestimmtes R-Bäume und KD-BäumeSpeichern Sie räumliche Daten effizient. Sie eignen sich gut für geografische Kartenkoordinatendaten und VLSI-Orts- und Routenalgorithmen und manchmal für die Nearest-Neighbor-Suche.

Bit-Arrays speichert einzelne Bits kompakt und ermöglicht schnelle Bitoperationen.


92



Reißverschlüsse - Ableitungen von Datenstrukturen, die die Struktur modifizieren, um eine natürliche Vorstellung von "Cursor" - aktueller Ort zu haben. Diese sind wirklich nützlich, da sie garantieren, dass die Indizes nicht außerhalb der Grenzen liegen können. in dem xmonad Fenstermanager um zu verfolgen, welches Fenster sich konzentriert hat.

Erstaunlicherweise können Sie sie ableiten Anwendung von Techniken aus der Infinitesimalrechnung zum Typ der ursprünglichen Datenstruktur!


87



Hier sind ein paar:

  • Suffix versucht. Nützlich für fast alle Arten der String-Suche (http://en.wikipedia.org/wiki/Suffix_trie#Funktionalität). Siehe auch Suffix-Arrays; Sie sind nicht ganz so schnell wie Suffixbäume, aber viel kleiner.

  • Bäume spreizen (wie oben erwähnt). Der Grund, warum sie cool sind, ist dreifach:

    • Sie sind klein: Sie benötigen nur die linken und rechten Zeiger wie in jedem Binärbaum (keine Knotenfarbe oder Größeninformationen müssen gespeichert werden)
    • Sie sind (vergleichsweise) sehr einfach zu implementieren
    • Sie bieten eine optimale amortisierte Komplexität für eine ganze Reihe von "Messkriterien" (Log-n-Lookup-Zeit ist die, die jeder kennt). Sehen http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems
  • Heap-ordered Suchbäume: Sie speichern eine Reihe von (Schlüssel, prio) Paare in einem Baum, so dass es ein Suchbaum in Bezug auf die Schlüssel und Heap-Reihenfolge in Bezug auf die Prioritäten ist. Man kann zeigen, dass ein solcher Baum eine einzigartige Form hat (und nicht immer vollständig nach oben und nach links gepackt ist). Mit zufälligen Prioritäten gibt es Ihnen die erwartete Suchzeit O (log n), IIRC.

  • Eine Nische sind Adjazenzlisten für ungerichtete planare Graphen mit O (1) Nachbarschaftsabfragen. Dies ist nicht so sehr eine Datenstruktur als eine bestimmte Art, eine vorhandene Datenstruktur zu organisieren. Hier ist, wie Sie es tun: Jeder planare Graph hat einen Knoten mit einem Grad von höchstens 6. Wählen Sie einen solchen Knoten, legen Sie seine Nachbarn in seine Nachbarliste, entfernen Sie sie aus dem Graphen und rekursiv, bis der Graph leer ist. Wenn Sie ein Paar (u, v) erhalten, suchen Sie in der Nachbarliste von v und in der Nachbarliste von v nach u. Beide haben eine Größe von höchstens 6, also ist dies O (1).

Mit dem obigen Algorithmus haben Sie, wenn Sie u und v Nachbarn sind, nicht beide in der Liste von v und in der Liste von v. Wenn Sie dies benötigen, fügen Sie einfach die fehlenden Nachbarn jedes Knotens zur Nachbarliste dieses Knotens hinzu, aber speichern Sie, wie viel von der Nachbarliste Sie für eine schnelle Suche durchsehen müssen.


69



Ich denke, dass Lock-Free-Alternativen zu Standard-Datenstrukturen, z. B. blockierungsfreie Warteschlange, Stapel und Liste, viel übersehen werden.
Sie sind zunehmend relevant, da die Nebenläufigkeit zu einer höheren Priorität wird und ein viel bewunderungswürdigeres Ziel ist als die Verwendung von Mutexen oder Sperren zum Behandeln von gleichzeitigem Lesen / Schreiben.

Hier sind einige Links
http://www.cl.cam.ac.uk/research/srg/netos/lock-free/
http://www.research.ibm.com/people/m/michael/podc-1996.pdf [Links zu PDF]
http://www.boyet.com/Articles/LockfreeStack.html 

Mike Actons (oft provokativ) Blog hat einige ausgezeichnete Artikel über lock-freie Design und Ansätze


65



Ich denke Disjunktes Set ist ziemlich geschickt für Fälle, in denen Sie eine Reihe von Elementen in verschiedene Mengen aufteilen und die Mitgliedschaft abfragen müssen. Eine gute Implementierung der Union- und Find-Operationen führt zu amortisierten Kosten, die effektiv konstant sind (umgekehrt zu Ackermanns Funktion, wenn ich meine Datenstrukturklasse richtig erinnere).


55



Fibonacci Haufen

Sie werden in einigen der am schnellsten bekannten Algorithmen (asymptotisch) für viele graphenbezogene Probleme verwendet, z. B. für das Kürzeste-Pfad-Problem. Der Dijkstra-Algorithmus läuft in O (E log V) -Zeit mit Standard-Binär-Heaps; Fibonacci-Heaps verbessern das auf O (E + V log V), was eine enorme Beschleunigung für dichte Graphen darstellt. Leider haben sie jedoch einen hohen konstanten Faktor, was sie in der Praxis oft unpraktisch macht.


52