793 Stimmen

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 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.

270voto

David Phillips Punkte 10204

Versucht auch bekannt als Präfix-Bäume oder Kritik-Bäume gibt es schon seit über 40 Jahren, aber sie sind noch relativ unbekannt. Eine sehr coole Anwendung von Tries wird in " TRASH - Eine dynamische LC-Trie- und Hash-Datenstruktur ", das ein Trie mit einer Hash-Funktion kombiniert.

12 Stimmen

Sehr häufig von Rechtschreibprüfungsprogrammen verwendet

0 Stimmen

Eine interessante Variante sind auch Burst-Versuche, bei denen man nur ein Präfix der Zeichenketten als Knoten verwendet und ansonsten Listen von Zeichenketten in den Knoten speichert.

0 Stimmen

Die Regex-Engine in Perl 5.10 erstellt automatisch Tries.

231voto

lacop Punkte 1944

Bloom-Filter : Bit-Array aus m Bits, die zunächst alle auf 0 gesetzt sind.

Um ein Element hinzuzufügen, führen Sie es durch k Hash-Funktionen, die Ihnen k Indizes in dem 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 sich daraus eine gewisse Wahrscheinlichkeit für falsch-positive Ergebnisse (laut Wikipedia etwa 0,61^(m/n), wobei n die Anzahl der eingefügten Elemente ist). Falsch-negative Ergebnisse sind nicht möglich.

Es ist unmöglich, einen Gegenstand zu entfernen, aber Sie können Zählbloomfilter , dargestellt durch ein Array von Ints und Inkrement/Dekrement.

20 Stimmen

Sie haben vergessen, ihre Verwendung mit Wörterbüchern zu erwähnen :) Man kann ein komplettes Wörterbuch in einen Bloomfilter mit etwa 512k quetschen, wie eine Hashtabelle ohne die Werte

8 Stimmen

Google führt die Verwendung von Bloom-Filtern in seiner Implementierung von BigTable an.

4 Stimmen

Dies ist also nützlich, weil es uns erlaubt, kostengünstig auf die Existenz eines Elements in einer Menge zu testen? (Ich bin neu bei Bloom-Filtern.)

139voto

Patrick Punkte 86090

Seil : Es handelt sich um eine Zeichenkette, die billige Voranstellungen, Teilzeichenketten, mittlere Einfügungen und Anfügungen ermöglicht. Ich habe wirklich nur einmal Verwendung für sie hatte, aber keine andere Struktur würde ausgereicht haben. Normale Strings und Arrays Prepends waren einfach viel zu teuer für das, was wir tun mussten, und Umkehrung alles war nicht in Frage.

15 Stimmen

Es gibt eine Implementierung in der SGI STL (1998): sgi.com/tech/stl/Seil.html

2 Stimmen

Ohne zu wissen, wie es heißt, habe ich kürzlich etwas sehr Ähnliches für Java geschrieben - die Leistung war hervorragend: code.google.com/p/mikeralib/source/browse/trunk/Mikera/src/

0 Stimmen

Seile sind ziemlich selten: stackoverflow.com/questions/1863440/

126voto

mmcdole Punkte 88559

Listen überspringen sind ziemlich toll.

Wikipedia
Eine Sprungliste ist eine probabilistische Datenstruktur, die auf mehreren parallelen, sortierten verknüpften Listen basiert und deren Effizienz mit der eines binären Suchbaums vergleichbar ist (durchschnittliche Zeit log n für die meisten Operationen).

Sie können als Alternative zu ausgeglichenen Bäumen verwendet werden (mit probalistischem Ausgleich anstelle einer strikten Durchsetzung des Ausgleichs). Sie sind einfach zu implementieren und schneller als z.B. ein rot-schwarzer Baum. Ich denke, sie sollten in der Werkzeugkiste eines jeden guten Programmierers sein.

Wenn Sie eine ausführliche Einführung in die Skip-Listen erhalten möchten, finden Sie hier eine Link zu einem Video der MIT-Vorlesung "Introduction to Algorithms" über sie.

Auch, aquí ist ein Java-Applet zur visuellen Veranschaulichung von Skip Lists.

2 Stimmen

Redis verwendet Sprunglisten, um "Sorted Sets" zu implementieren.

0 Stimmen

Interessante Nebenbemerkung: Wenn Sie genügend Ebenen zu Ihren Überspringungslisten hinzufügen, erhalten Sie im Wesentlichen einen B-Baum.

91voto

Yuval F Punkte 20547

Räumliche Indizes insbesondere R-Bäume y KD-Bäume Geodaten effizient speichern. Sie eignen sich gut für geografische Kartenkoordinatendaten und VLSI-Orts- und Routenalgorithmen sowie manchmal für die Suche nach dem nächsten Nachbarn.

Bit-Arrays speichern einzelne Bits kompakt und ermöglichen schnelle Bitoperationen.

6 Stimmen

Räumliche Indizes sind auch für N-Körper-Simulationen nützlich, bei denen weitreichende Kräfte wie die Schwerkraft wirken.

CodeJaeger.com

CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.

Powered by:

X