Wie kann das Laden großer Hashtabellen beschleunigt werden?

7

Wie ich aus dem Handbuch (letzte Absätze von http://www.gnu.org/software/emacs/manual/html_node/elisp/Creating-Hash.html ) und der Frage /programming/11745097 verstehe / Beim Stackoverflow kann eine gedruckte Version einer Hashtabelle auf der Disc gespeichert werden, um sie zur späteren Verwendung zu laden.

Zum Beispiel die gedruckte Version einer Hashtabelle, die von erstellt wurde

(setq ht (make-hash-table :test 'equal))
(puthash "orange" 1 ht)
(puthash "apple" 2 ht)

ist wie folgt

#s(hash-table size 65 test equal rehash-size 1.5 rehash-threshold 0.8 data ("orange" 1 "apple" 2))

Ist diese gedruckte Version bereits das beste Format (aus Gründen der Geschwindigkeit), das Emacs verwenden kann? Gibt es ein spezielles Verfahren zum Neuformatieren (Byte-Kompilieren, Ändern) des oben gedruckten Formats in ein besseres Format (möglicherweise nur maschinenlesbar), damit Emacs diese Hashtabelle schneller lädt? Wenn die Antwort positiv ist, wie geht das?

hash-tables Name
quelle

Antworten:

3

Ja, es ist das beste Format (aus Gründen der Geschwindigkeit).

Stefan
quelle
Ich akzeptiere deinen Eid.
Name
5

Sie müssen jeden Wert hashen und einfügen, egal was passiert, und wenn Sie nicht mit riesigen Hash-Tabellen zu tun haben, sollte die aufgewendete Zeit eigentlich keine Rolle spielen. Wenn Ihre Tabellen jedoch groß sind, sollten Sie den :sizeParameter verwenden, make-hash-tabledamit keine Neuzuweisungen erfolgen müssen. Wenn eine Hash-Tabelle den Schwellenwert erreicht, ist es ein großer Leistungsverlust, einen neuen Speicherplatz neu zuzuweisen, um die Werte zu speichern und alle aktuellen Einträge erneut zu verarbeiten.

Wenn Sie wissen, dass Sie 1 Million Einträge in eine Hash-Tabelle einfügen möchten, verwenden Sie (make-hash-table :size 1000000)

Betrachten Sie den folgenden Benchmark:

(benchmark 10
           '(let ((ht (make-hash-table :size 1000000)))
              (dotimes (n 1000000) (puthash n (1+ n) ht))
              ht))
"Elapsed time: 4.156233s (2.087411s in 10 GCs)"


(benchmark 10
           '(let ((ht (make-hash-table)))
              (dotimes (n 1000000) (puthash n (1+ n) ht))
              ht))
"Elapsed time: 10.276816s (7.713422s in 41 GCs)"

Sie können auch Ihre eigene Test- und Hash-Funktion für Hash-Tabellen definieren. Wenn Sie wissen, dass sich Ihre Schlüssel in einem bestimmten Satz befinden, können Sie möglicherweise schnellere Gleichheits- und Hashing-Funktionen schreiben, die dies ausnutzen. Siehe : define-hash-table-test.

Jordon Biondo
quelle
Sehr interessanter Zeitvergleich. Vielen Dank. Wie Sie gezeigt haben, kann das Festlegen der Größe einer Hash-Tabelle die Erstellungszeit erheblich beeinflussen.
Name
Lassen Sie mich jedoch erwähnen, dass ich in der ursprünglichen Frage nach der Geschwindigkeit aus einem etwas anderen Blickwinkel gefragt habe. Ich habe bereits eine große Hash-Tabelle erstellt und diese Hash-Tabelle bereits auf der Disc gespeichert (per Druckbefehl). Ich habe also eine große Datei, deren Inhalt wie ist #s(hash-table size 65 test equal rehash-size 1.5 rehash-threshold 0.8 data ("orange" 1 "apple" 2 ..............)). Ich kann diese Hash-Tabelle laden. Ich war interessiert zu wissen, ob dieser Dateityp das beste Format ist, das Emacs verwenden kann, um die Tabelle schnell zu laden.
Name
Der Schwerpunkt liegt also eher auf dem Zeitpunkt des Ladens einer bereits gespeicherten Tabelle auf der Disc als auf dem Zeitpunkt der erstmaligen Erstellung.
Name