Wie wähle ich eine funktionale Wörterbuchdatenstruktur aus?

10

Ich habe ein bisschen über die folgenden Datenstrukturen gelesen:

  • Bagwells ideale Hash-Versuche
  • Larsons dynamische Hash-Tabellen
  • Rot-schwarze Bäume
  • Patricia Bäume

... und ich bin sicher, es gibt viele andere da draußen. Ich habe sehr wenig darüber gesehen, wofür jeder besser geeignet ist oder warum ich einen anderen vorziehen würde. Hier sind einige Fragen in diese Richtung:

  1. Welche funktionalen Wörterbuchdatenstrukturen sind wichtig zu wissen?
  2. Was sind die Vor- und Nachteile dieser Ansätze?
  3. Wann ist es sinnvoller, eine zwingendere Datenstruktur zu verwenden?

Die Nummern 2 und 3 sind jedoch die wichtigeren. :-)

Jason
quelle
Verwandte: Was ist neu in rein funktionalen Datenstrukturen seit Okasaki? (Diese Frage ist nicht auf Wörterbücher beschränkt.)
Tsuyoshi Ito
Diese Frage (außer dem Punkt mit der Nummer 3) hat das Gefühl einer [großen Liste].
Kaveh
2
Es wäre hilfreich zu wissen, ob die oben verlinkte Frage Ihre Bedenken anspricht, und wenn nicht, warum nicht?
Suresh Venkat
@Suresh - Das beantwortet # 1, aber 2 und 3 waren die wichtigeren. Ich suche hauptsächlich nach einer Gesamtübersicht, damit ich herausfinden kann, welche es wert sind, eingehender untersucht zu werden.
Jason
2
okay. Es könnte sich also lohnen, die Frage zu bearbeiten.
Suresh Venkat

Antworten:

16

Ich kann # 2 nicht wirklich beantworten, ohne mich zu verlaufen (es gibt zu viele Dimensionen, entlang derer Sie diese Strukturen vergleichen können), aber für # 3 ist die Antwort ziemlich einfach.

Verwenden Sie eine zwingende Datenstruktur, wenn: (a) absolut kein Aliasing vorliegt oder (b) Sie Aliasing wirklich für eine effiziente Übertragung verwenden müssen.

Wenn es überhaupt kein Aliasing Ihrer Datenstruktur gibt, nutzen Sie nicht die Tatsache, dass funktionale Datenstrukturen persistent sind. Es gibt also keinen Grund, für ihre Kosten zu bezahlen. Dieser Rat hat zwei Vorbehalte. Erstens mögen Sie die Einfachheit der Implementierung einer funktionalen Datenstruktur bevorzugen: Wenn Sie das Löschen für einen funktionierenden rot-schwarzen Baum implementieren, werden Sie verflucht, aber wenn Sie das Löschen in einem zwingenden rot-schwarzen Baum mit übergeordneten Zeigern implementieren, werden Sie über Selbstmord nachdenken. Zweitens kann die Zuweisung in einer gc-Sprache teurer sein als erwartet, da durch Schreibvorgänge Datenstrukturen aus der jungen Generation entfernt werden können. Wir haben wirklich keine gute Theorie zu Cache-Effekten und GC, daher haben Sie keine andere Wahl, als Benchmarking durchzuführen.

Zweitens, wenn Sie einen Broadcast-Kanal benötigen, ist eine gemeinsam genutzte Datenstruktur eine hervorragende Möglichkeit, dies zu tun. Mit einer zeitkonstanten Aktualisierung können Sie beliebig vielen anderen Personen mitteilen, dass sich ein Wert geändert hat. (Aus diesem Grund ist Union-Find eine so großartige Datenstruktur.) Bei einem rein funktionalen Setup müssen Sie entweder alle anderen Personen ändern oder ihnen abstrakte Zeiger in einen Zustand geben, den Sie manuell codieren (was eine Art stumpf ist) etwas zu tun).

Wenn Sie entweder nicht über Aliasing und Objektbesitz nachdenken möchten oder wenn Sie mehrere Versionen derselben Datenstruktur benötigen (Sie benötigen beispielsweise sowohl eine neue als auch eine alte Version), verwenden Sie einfach eine funktionale Datenstruktur.

Der Ort, an dem ich es am schwierigsten finde, diesem Rat zu folgen, sind Graph-Algorithmen. Es gibt viele wirklich elegante imperative Graph-Algorithmen, aber es ist häufig der Fall (z. B. beim Schreiben von Compilern), dass Sie auch Persistenz wünschen. Normalerweise versuchen die Leute, den Unterschied aufzuteilen und den coolen Imperativ-Algorithmus zu verwenden, aber versuchen, die Versionierung auf die Seite zu schrauben, um die Persistenz zu erhalten. Dies ist im Allgemeinen ziemlich schrecklich, voller Fehler und neigt dazu, den Leistungsvorteil des imperativen Algorithmus zu verlieren.

Neel Krishnaswami
quelle
2
Was ist Aliasing in diesem Zusammenhang?
Suresh Venkat
6
Aliasing ist, wenn Sie mehrere Verweise auf dasselbe Datenelement haben. Wenn diese Daten veränderbar sind, müssen bei der Begründung eines Programms, das sie verwendet, alle anderen Unterprogramme, die darauf zugreifen und sie ändern können, explizit berücksichtigt werden. Wenn dieses Datenelement unveränderlich ist, können Sie lokal über ein Programm nachdenken, das es verwendet, und Aliasing ignorieren, da Sie wissen, dass niemand, der auf die Daten zugreifen kann, es ändern kann.
Neel Krishnaswami
"Wenn Sie jedoch das Löschen in einem zwingenden rot-schwarzen Baum mit übergeordneten Zeigern implementieren, werden Sie über Selbstmord nachdenken." Schauen Sie sich Sedgewicks linksgerichtete rot-schwarze Bäume an. Der allgemeine Fall des Löschens wird durch einen Standardtrick auf "delete-min" reduziert, und "delete-min" selbst ist für LLRB-Bäume sehr einfach. Keine übergeordneten Zeiger erforderlich.
Per Vognsen
1
"Dies ist im Allgemeinen ziemlich schrecklich, voller Fehler und neigt dazu, den Leistungsvorteil des imperativen Algorithmus zu verlieren." Norman Ramseys Artikel über die Verwendung von Reißverschlüssen für Kontrollflussdiagramme in einem optimierenden Compiler liefert ein Beispiel für einen überzeugenden Kompromiss. Sie haben effektiv einen lokalen Heap für die Unterstützung einer einfachen und effizienten Neuverdrahtung von Referenzen zwischen Basisblöcken in einem CFG, aber die Manipulation des Inhalts von Basisblöcken ist funktional (oder semi-funktional, abhängig von Ihrer philosophischen Sicht auf Reißverschlüsse).
Per Vognsen
1

Welche funktionalen Wörterbuchdatenstrukturen sind wichtig zu wissen?

Höhenausgeglichene Binärbäume und deren Versuche sind ein guter Allround-Kompromiss. Ebenfalls:

  • Patricia Bäume.
  • Hash versucht es.

Was sind die Vor- und Nachteile dieser Ansätze?

Höhenausgeglichene Binärbäume und deren Versuche sind ein guter Kompromiss für Atomschlüssel. Versuche sind die gleichen für Schlüssel, die Sequenzen sind, z. B. String-Schlüssel.

Patricia-Bäume können um ein Vielfaches schneller sein, erlauben jedoch nur Ganzzahlschlüssel.

Hash-Versuche können um ein Vielfaches schneller sein als ausgeglichene Binärbäume, insbesondere wenn Hashing billiger als Vergleich ist und Polymorphismus einen Overhead hat (z. B. Zeichenfolgen in .NET) und das Schreiben von Zeigern in den Heap schnell ist (z. B. VMs wie JVM und CLR) eher für imperative Sprachen als für funktionale Sprachen optimiert). Hash-Versuche erlauben auch die interne Verwendung von Mutationen als Optimierung.

Rot-schwarze Bäume sind weniger wichtig, da sie keine signifikanten Vorteile gegenüber Bäumen mit ausgeglichener Höhe haben, aber den signifikanten Nachteil haben, dass sie keine effiziente Vereinigung, Kreuzung und Differenzierung ermöglichen.

Ebenso sind Fingerbäume in der Praxis nicht viel besser.

Wann ist es sinnvoller, eine zwingendere Datenstruktur zu verwenden?

Wenn Ihr Wörterbuch einmal ausgefüllt und dann nur für Suchvorgänge verwendet wird, dh eingefroren.

Wenn Sie Leistung benötigen (eine anständige Hash-Tabelle wie .NET Dictionaryist normalerweise 10-40 × schneller als jedes generische rein funktionale Wörterbuch).

Wenn Sie ein schwaches Wörterbuch benötigen, weil kein rein funktionales schwaches Wörterbuch bekannt ist.

Jon Harrop
quelle