Ich frage mich, ob das Erlang OTP dict Modul als Hash-Tabelle implementiert ist und in diesem Fall gibt es die Leistung von solchen?Zeit Komplexität von erlang dict
Durchschnitt Fall
Search: O(1 + n/k)
Insert: O(1)
Delete: O(1 + n/k)
Worst Case
Search: O(n)
Insert: O(1)
Delete: O(n)
Quelle: Wikipedia Hash Table
Da das Modul dict ist in Erlang selbst mit den integrierten Datentypen (Tupel und Listen) implementiert, und ist nicht destruktiv, das heißt, jedes "Update" tatsächlich erstellt eine leicht neu geschriebene neue Version des vorherigen dict, die Zeitkomplexität kann niemals besser sein als logarithmisch (die Implementierung muss eine Art Baum verwenden), aber die Details können mit der Implementierung variieren.
Die aktuelle Implementierung (die seit vielen Jahren existiert) skaliert nicht wirklich gut, wenn die Anzahl der Einträge groß wird. Der Autor (Robert Virding) experimentierte kürzlich mit anderen Baumimplementierungen wie 2-3-Bäumen, und es ist möglich, dass die Standardimplementierung des dict-Moduls in einer zukünftigen Version geändert wird. Siehe http://erlang.org/pipermail/erlang-questions/2012-June/067311.html
Wenn Sie an solchen Dingen interessiert sind, möchten Sie vielleicht mehr über reine funktionale Datenstrukturen lesen. Dies scheint ein guter Ausgangspunkt zu sein: http://en.wikipedia.org/wiki/Purely_functional (insbesondere die Verbindung zu Okasakis These).
Nun, hier ein wenig aus meiner Liga. Vor allem ist es eine Hashtabelle, aber ich bin mir nicht sicher über die Ausführungszeit.
an der Quelle der Suche nach dem dict-Modul (lib/stdlib/src/dict.erl), zeigt:
%% We use the dynamic hashing techniques by Per-�ke Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend. Much of the
%% terminology comes from that paper as well.
über dieses Papier Googeln zeigt eine Reihe von Links mit dem PDF in Frage, dass Sie kann für die technischen Details der Implementierung verweisen (auch, es gibt mehr Kommentare im Quellcode, die nützlich sein könnten)
Hoffe es wirft etwas Licht auf es!