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

Question

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

Jeder kennt verknüpfte Listen, binäre Bäume und Hashes, aber was ist mit Listen überspringen y Bloom-Filter zum Beispiel. Ich würde gerne mehr Datenstrukturen kennenlernen, die nicht so häufig vorkommen, aber wissenswert sind, weil sie auf großartigen Ideen beruhen und den Werkzeugkasten eines Programmierers bereichern.

PS: Ich interessiere mich auch für Techniken wie Tanzende Links die sich die Eigenschaften einer gemeinsamen Datenstruktur zunutze machen.

EDIT : Bitte versuchen Sie Links einbeziehen zu Seiten, die die Datenstrukturen genauer beschreiben. Versuchen Sie auch, ein paar Worte zu folgenden Themen hinzuzufügen warum eine Datenstruktur ist cool (als Jonas Kölker bereits hervorgehoben). Versuchen Sie außerdem, Folgendes bereitzustellen eine Datenstruktur pro Antwort . Dadurch können sich die besseren Datenstrukturen allein aufgrund ihrer Stimmen an die Spitze setzen.

Answer 1

Reißverschlüsse - Ableitungen von Datenstrukturen, die die Struktur so verändern, dass sie einen natürlichen Begriff von "Cursor" - aktuelle Position - haben. Diese sind sehr nützlich, da sie garantieren, dass Indikatoren nicht außerhalb der Begrenzung liegen können -- verwendet z.B. in der xmonad window manager um zu verfolgen, welches Fenster fokussiert wurde.

Erstaunlich ist, dass man sie ableiten kann durch Anwendung von Techniken aus der Infinitesimalrechnung auf den Typ der ursprünglichen Datenstruktur!

Answer 2

Hier sind einige davon:

• Suffix-Versuche. Nützlich für fast alle Arten der Stringsuche ( http://en.wikipedia.org/wiki/Suffix_trie#Functionality ). Siehe auch Suffix-Arrays; sie sind nicht ganz so schnell wie Suffix-Bäume, aber viel kleiner.

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

  • Sie sind klein: Sie brauchen nur die linken und rechten Zeiger, wie in jedem Binärbaum (keine Informationen über die Farbe oder Größe der Knoten müssen gespeichert werden).
  • Sie sind (vergleichsweise) sehr einfach zu implementieren
  • Sie bieten optimale amortisierte Komplexität für eine ganze Reihe von "Messkriterien" (wobei die log n-Nachschlagezeit das bekannteste ist). Siehe http://en.wikipedia.org/wiki/Splay_tree#Performance_theorems

• Heap-geordnete Suchbäume: Man speichert einen Haufen von (Schlüssel, Priorität) Paaren in einem Baum, so dass es ein Suchbaum in Bezug auf die Schlüssel und heap-geordnet in Bezug auf die Prioritäten ist. Man kann zeigen, dass ein solcher Baum eine eindeutige Form hat (und nicht immer vollständig nach oben und nach links gepackt ist). Mit zufälligen Prioritäten erhält man eine erwartete Suchzeit von O(log n), IIRC.

• Eine Nische sind Adjazenzlisten für ungerichtete planare Graphen mit O(1) Nachbarschaftsabfragen. Dabei handelt es sich weniger um eine Datenstruktur als um eine besondere Art, eine bestehende Datenstruktur zu organisieren. So wird es gemacht: Jeder planare Graph hat einen Knoten mit einem Grad von höchstens 6. Man wählt einen solchen Knoten aus, trägt seine Nachbarn in seine Nachbarliste ein, entfernt ihn aus dem Graphen und rekursiert, bis der Graph leer ist. Wenn ein Paar (u, v) gegeben ist, suchen Sie nach u in der Nachbarliste von v und nach v in der Nachbarliste von u. Beide haben eine Größe von höchstens 6, also ist dies O(1).

Wenn u und v Nachbarn sind, wird nach dem obigen Algorithmus nicht sowohl u in der Liste von v als auch v in der Liste von u stehen. Wenn Sie dies benötigen, fügen Sie einfach die fehlenden Nachbarn eines jeden Knotens zur Nachbarliste dieses Knotens hinzu, aber speichern Sie, wie viel von der Nachbarliste Sie für eine schnelle Suche durchsehen müssen.

Answer 3

Ich denke, dass sperrfreie Alternativen zu Standarddatenstrukturen, d.h. sperrfreie Warteschlangen, Stacks und Listen, viel zu wenig beachtet werden.
Sie werden immer wichtiger, da die Gleichzeitigkeit eine höhere Priorität erhält, und sind ein viel bewundernswerteres Ziel als die Verwendung von Mutexes oder Sperren zur Handhabung gleichzeitiger Lese-/Schreibvorgänge.

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 Acton's (oft provokative) Blog hat einige ausgezeichnete Artikel über schlossfreies Design und Ansätze

Answer 4

Ich glaube Disjunkte Menge ist sehr nützlich, wenn Sie eine Reihe von Elementen in verschiedene Mengen aufteilen und die Zugehörigkeit abfragen müssen. Eine gute Implementierung der Operationen "Vereinigen" und "Suchen" führt zu amortisierten Kosten, die effektiv konstant sind (Umkehrung der Ackermnanschen Funktion, wenn ich mich richtig an meinen Datenstrukturkurs erinnere).

Answer 5

Fibonacci-Haufen

Sie werden in einigen der (asymptotisch) schnellsten bekannten Algorithmen für viele Probleme im Zusammenhang mit Graphen verwendet, z. B. für das Problem des kürzesten Weges. Dijkstras Algorithmus läuft mit Standard-Binärhaufen in O(E log V)-Zeit; die Verwendung von Fibonacci-Haufen verbessert diese Zeit 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.