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

<zvrba> Van-Emde-Boas-Bäume

Ich denke, es wäre nützlich zu wissen warum sie sind cool. Im Allgemeinen ist die Frage nach dem "Warum" die wichtigste Frage ;)

Meine Antwort ist, dass man damit O(log log n)-Wörterbücher mit {1..n} Schlüsseln erhält, unabhängig davon, wie viele der Schlüssel gerade verwendet werden. Genauso wie man durch wiederholtes Halbieren O(log n) erhält, erhält man durch wiederholtes Quadrieren O(log log n), was auch im vEB-Baum geschieht.

Answer 2

Wie wäre es mit Bäume spreizen ?

Außerdem ist Chris Okasakis rein funktionale Datenstrukturen kommen mir in den Sinn.

Answer 3

Eine interessante Variante der Hashtabelle ist die Cuckoo Hashing . Es verwendet mehrere Hash-Funktionen anstelle von nur einer, um Hash-Kollisionen zu vermeiden. Kollisionen werden aufgelöst, indem das alte Objekt von dem durch die primäre Hashfunktion angegebenen Ort entfernt und an einen durch eine alternative Hashfunktion angegebenen Ort verschoben wird. Cuckoo Hashing ermöglicht eine effizientere Nutzung des Speicherplatzes, da der Auslastungsfaktor mit nur 3 Hash-Funktionen auf bis zu 91 % erhöht werden kann und trotzdem eine gute Zugriffszeit gewährleistet ist.

Answer 4

A Min-Max-Haufen ist eine Variante einer Haufen die eine doppelendige Prioritätswarteschlange implementiert. Erreicht wird dies durch eine einfache Änderung der Heap-Eigenschaft: Ein Baum gilt als min-max geordnet, wenn jedes Element auf geraden (ungeraden) Ebenen kleiner (größer) ist als alle Unter- und Großkinder. Die Ebenen sind von 1 an nummeriert.

http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg

Answer 5

Ich mag Cache Oblivious Datastructures . Die Grundidee besteht darin, einen Baum in rekursiv kleineren Blöcken anzulegen, so dass Caches vieler verschiedener Größen die Vorteile von Blöcken nutzen können, die in sie passen. Dies führt zu einer effizienten Nutzung der Zwischenspeicherung auf allen Ebenen, vom L1-Cache im Arbeitsspeicher bis hin zu großen Datenpaketen, die von der Festplatte gelesen werden, ohne dass die Größe einer dieser Zwischenspeicherschichten bekannt sein muss.