Ich habe eine Hash-Tabelle, wo die Schlüssel ziemlich komplexe Listen sind, mit Unterlisten von Symbolen und Ganzzahlen, und der Wert sollte in Abhängigkeit von dem bereits vorhandenen Wert geändert werden. Die Tabelle wird mit :test #'equal erstellt.
Ich mache etwas ähnliches:
%Vor% Profiling zeigt, dass equal -Tests viel Zeit benötigen. Ich habe eine Optimierungsidee, dass die Anzahl der gethash Lookups von zwei auf eins reduziert werden könnte. Dies kann in C ++ geschehen, indem der Iterator wiederverwendet wird, aber nicht sicher, wie dies in Lisp geschehen würde. Irgendwelche Ideen?
Machen Sie nichts Besonderes, weil die Implementierung es für Sie erledigt.
Natürlich ist dieser Ansatz implementierungsspezifisch, und die Leistung der Hash-Tabelle variiert zwischen den Implementierungen. (Aber dann sind Optimierungsfragen immer implementierungsspezifisch.)
Die folgende Antwort gilt für SBCL. Ich empfehle zu überprüfen, ob die Hash-Tabellen von Lisp die gleiche Optimierung durchführen. Beschweren Sie sich bei Ihrem Lieferanten, wenn sie es nicht tun!
Was in SBCL passiert, ist, dass die Hashtabelle den letzten Tabellenindex, auf den GETHASH zugreift, zwischenspeichert.
Wenn PUTHASH (oder äquivalent, (SETF GETHASH)) aufgerufen wird, prüft es zuerst, ob der Schlüssel in diesem zwischengespeicherten Index EQ zu dem Schlüssel ist, den Sie übergeben.
Wenn dies der Fall ist, wird die gesamte Hashtabellen-Suchroutine umgangen, und PUTHASH wird direkt im zwischengespeicherten Index gespeichert.
Beachten Sie, dass EQ nur ein Zeigervergleich ist und daher extrem schnell ist - es muss die Liste überhaupt nicht durchlaufen.
In Ihrem Codebeispiel ist das also überhaupt kein Overhead.
Sie können tatsächlich dreimal auf die Hash-Tabelle zugreifen. Warum? Weil das push -Makro in Code mit einem gethash expandieren kann, um die Liste zu erhalten, und dann mit einer% system::sethash -Operation, um den Wert zu speichern.
In diesem Problem untersuchen Sie den Wert eines Ortes, der eine Liste ist. Wenn diese Liste einen Prädikatstest erfüllt, dann drücken Sie etwas an diesen Ort.
Dieses Problem kann durch Erstellen eines Spezialoperators, der diese Semantik erfasst, angegriffen werden:
%Vor%Zum Beispiel:
%Vor% Dieser push-if ist als ein Makro definiert, das die Funktion get-setf-expansion für das Argument <place> form verwendet, um die Teile zu erhalten, die benötigt werden, um den Code zum einmaligen Zugriff auf diesen Ort zu generieren.
Der generierte Code wertet ein Ladeformular aus, um den alten Wert von der Stelle abzurufen, wendet dann die Bedingung auf den alten Wert an, und wenn er erfolgreich ist, bereitet er den neuen Wert in der entsprechenden temporären Speichervariablen aus get-setf-expansion vor. und wertet das Geschäftsformular aus.
Dies ist das Beste, was Sie in portablem Lisp tun können, und Sie können feststellen, dass dies immer noch zwei Hash-Operationen ausführt, wie oben erwähnt. (In diesem Fall hoffen Sie, dass es eine anständige Caching-Optimierung in der Hash-Tabelle selbst gibt. Aber zumindest ist es auf zwei Ops zurückzuführen.)
Der Ansatz wird so optimiert wie die eingebauten mutierenden Formulare: incf , push , rotatef usw. Unser push-if wird mit den eingebauten Werten gleichwertig sein.
Wenn es immer noch saugt (führt zwei Hashes aus, um einen Hash-Platz zu aktualisieren, ohne Caching-Optimierung), dann ist die einzige Möglichkeit, das zu beheben, die Implementierungsebene.
push-if code folgt:
Beispielerweiterung:
%Vor% Sieht gut aus für den einfachen Fall, wenn der Ort eine Variable ist. Es gibt nur ein kleines Problem, das ich nicht beheben will: Die Formulare new , test und place werden jeweils nur einmal ausgewertet, aber nicht von links nach rechts!
Test mit einem Hash-Tabellenplatz (CLISP):
%Vor% Aha; Jetzt wird ein etwas interessanterer Code erzeugt, um zu vermeiden, dass a und b zweimal ausgewertet werden. Die Funktion gethash wird einmal aufgerufen, ihre Argumente sind jedoch gensym-Variablen. Der alte Wert wird als #:G12735 erfasst. Der Test wird auf ihn angewendet, und wenn er besteht, wird die Filialvariable #:G12734 mit dem alten Listenwert aktualisiert, wobei new davor steht. Dann wird dieser Wert in die Hash-Tabelle mit system::puthash eingefügt.
In dieser Lisp-Implementierung gibt es keine Möglichkeit, zwei Hashtabellenoperationen zu vermeiden, um eine Aktualisierung durchzuführen: gethash und system::puthash . Das ist das Beste, was wir tun können, und wir hoffen, dass die beiden als optimiertes Paar funktionieren.
Eine Sache, die Sie tun könnten, ist defstruct, um einen Wert zu erzeugen, auf den jeder Eintrag in Ihrer Hash-Tabelle zeigt. Ihre Liste von Werten (auf die Sie in Ihrem aktuellen Beispiel drängen) könnte dort gespeichert werden. Die Erstellung der Struktur könnte entweder in diesem ersten Gethash-Aufruf (als Standardwert) erfolgen oder manuell, wenn Sie feststellen, dass dort kein Wert vorhanden ist. Dann kann das Objekt in der Art, wie Sie es tun, seitenbetont werden.
(Dies ignoriert die Frage, ob Sie wirklich so komplexe Werte wie Ihre Hashtabellenschlüssel verwenden möchten oder ob es eine Möglichkeit gibt, das zu umgehen. Beispielsweise könnten Sie Strukturen / CLOS-Objekte anstelle von Komplexen verwenden Listen als Ihre Schlüssel, und dann könnten Sie stattdessen eine EQ-Hashtabelle verwenden. Aber das hängt sehr davon ab, was Sie tun.)
"Profiling zeigt, dass gleiche Tests sehr lange dauern."
Ja, aber haben Sie verifiziert, dass # 'EQUAL Hashtabellen-Lookups auch viel Zeit brauchen?
Haben Sie dies für Geschwindigkeit auf einem optimierenden Compiler wie SBCL kompiliert und die Anmerkungen des Compilers betrachtet?
Nachdem Sie diese beiden Fragen gelöst haben, können Sie auch eine verschachtelte Hash-Tabelle für jede Ebene Ihrer Listenschlüssel ausprobieren. Es sollte nicht schwer sein, ein Makro für beliebig verschachtelte Hash-Tabellen zu schreiben.
Vielleicht vermisse ich etwas Offensichtliches, aber:
%Vor%seit:
Edit: Ups, ich war: Ich habe den Fall vermisst, wo Old-I ist Null. Aber wenn das nicht der übliche Fall ist, dann kann es immer noch ein Gewinn sein, da Sie nur in diesem Fall nachschlagen müssen:
%Vor%Hmm, geht das?
Einige Problemumgehungen könnten sein:
Wenn das allgemeine Muster Nachschlagen ist - & gt; find-it - & gt; overwrite-it, dann könnten Sie den Werttyp durch eine Liste ersetzen, die den Werttyp enthält. Nachdem Sie das Wertobjekt für den Schlüssel gefunden haben, ersetzen Sie einfach sein erstes Element, z. B.
%Vor%Alternativ, wenn das allgemeine Muster eher wie Nachschlagen ist - & gt; es ist-nicht-dort - & gt; add-it, sollten Sie in Betracht ziehen, die Schlüssel selbst zu hashen und dann die Hash-Tabelle Ihren Hash-Wert als Schlüssel verwenden zu lassen. Dies kann komplizierter sein, abhängig von der Tiefe und Semantik dieser komplexen Listen. Im einfachsten Fall könnten Sie mit einer Hash-Funktion davonkommen, die (rekursiv) den Hash-Wert der Elemente ihres Listenarguments xor darstellt.
EDITED: Beantworten der Frage in den Kommentaren: Die Idee dahinter ist, dass die Hash-Tabelle, anstatt die Hash-Tabelle den Werten zuzuordnen, nun die Schlüssel den einzelnen Elementlisten zuordnet, wobei das Element der Wert ist. Dann können Sie den Inhalt dieser Listen ändern, ohne die Hash-Tabelle selbst zu berühren. Das Folgende stammt aus SBCL:
%Vor%Tags und Links lisp common-lisp