Ich versuche Hashtabellen in Haskell mit dem hashtables -Paket zu verwenden und zu finden, dass ich nirgendwohin komme in der Nähe von Pythons Leistung. Wie kann ich ähnliche Leistungen erzielen? Ist es möglich, aktuelle Haskell-Bibliotheken und Compiler zu geben? Wenn nicht, was ist das zugrunde liegende Problem?
Hier ist mein Python-Code:
%Vor%Hier ist mein entsprechender Haskell-Code:
%Vor% Hier ist eine andere Version mit Data.Map , die langsamer ist als beides für mich:
Interessanterweise funktioniert Data.HashMap sehr schlecht:
Mein Verdacht ist, dass Data.HashMap schlecht abschneidet, denn im Gegensatz zu Data.Map ist es nicht rückgratsicher (denke ich), also ist foldl' nur ein foldl mit den dazugehörigen Thunk-Buildup-Problemen.
Beachten Sie, dass ich -prof verwendet habe und überprüft habe, dass die meiste Zeit im Code hashtables oder Data.Map verbracht wird, nicht im forM oder ähnlichem. Der gesamte Code wird mit -O2 und anderen Parametern kompiliert.
Die Dokumentation für hashtables stellt fest, dass "Cuckoo Hashing, wie die grundlegende Implementierung der Hashtabelle mit linearer Abtastung, auch möglich ist leiden lange Verzögerungen, wenn die Tabelle in der Größe geändert wird. " Sie verwenden new , wodurch eine neue Tabelle der Standardgröße erstellt wird. Aus der Quelle , es scheint, dass die Standardgröße 2 ist. Das Einfügen von 10000000 Elementen führt wahrscheinlich zu zahlreichen Anpassungen.
Versuchen Sie es mit newSized .