Effiziente Immutable Map-Implementierung?

Question

Ich frage mich, ob es eine Implementierung einer Karte, die ist:

• Immutable, so dass ich es in funktionaler Programmierung verwenden kann, und mühelos Transaktionen und Parallelität gewährleisten.
• Schnell. Ich habe Binary Suche Bäume (RB, AVL) und versucht, aber keiner von ihnen schien so schnell wie Hash-Tabellen. Gibt es eine Karte Implementierung, die konstante Zeit unterstützt für Updates und Abfragen? (Oder zumindest sehr schnell logarithmische Zeit)

Kurz gesagt, ist es eine funktionelle Datenstruktur, die mit Hash Karten in der Leistung vergleichen?

Answer 1

Clojure hat unveränderliche Karten. (link). Nicht sicher, welche zugrunde liegende Datenstruktur verwendet wird. Clojure Quellcode gibt Ihnen mehr Informationen!

Answer 2

Scala hat auch immutable maps, aber sie sind langsamer als Hash-Tabellen. Ich vermute, die Antwort auf Ihre Frage ist nein, Sie werden keine unveränderliche Kartenimplementierung mit O (1) erwarteten Zeit einfügen/Abfrage-Operationen finden.

Answer 3

Wie auch immer, nur um mit Leuten zu teilen, sind dies zwei interessante Blogeinträge über Persistente Vektoren Implementierung in Scala mit Tries. Sie erwähnen auch die Implementierung von Clojure sowie die neue IntMap in den letzten Scala-Versionen.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

Für diese Datenstrukturen habe ich mit Schlüssel als ganze Zahlen getestet, aber noch nicht Saiten. Da meine reale Anwendung Zeichenfolgen als Schlüssel verwendet, bin ich mir nicht sicher, ob die Implementierung effizienter ist als eine Hash-Map. Was passiert, wenn ich den HashCode der Zeichenfolge als Schlüssel verwende und dann einen persistenten Vektor zur Unterstützung der Karte verwende? Ich werde einen 32-way Trie verwenden, um den persistenten Vektor zu implementieren. Ich denke, eine Kollision wäre sehr selten, und Speicher würde nur entsprechend ausgegeben werden. Aber ich bin mir nicht sicher über die tatsächliche Menge, die für das Kopieren von Updates benötigt wird.

Ich werde meine Ergebnisse bald posten.

Answer 4

Ich habe es nicht gelesen, aber ich denke, einige Leute betrachten Purely Functional Data Structures als die Bibel für diese Art von Sache.