O (1) term look up

Question

Ich möchte die Existenz eines Begriffes so schnell wie möglich in meinem aktuellen Prolog-Programm nachschlagen können, ohne dass die Prolog-Engine alle Begriffe durchläuft, bis sie schließlich den bestehenden Begriff erreicht.

Ich habe keinen Beweis dafür gefunden .. aber ich nehme an, dass

animal(lion). 
animal(zebra). 
... 
% thousands of other animals 
... 
animal(tiger). 

Der swi-prolog Motor, um mit Tigern zu vereinen versuchen, durch Tausende von Tieren gehen müssen gegeben, dass Tier zu bestätigen (Tiger) ist in meiner Prolog-Datenbank.

In anderen Sprachen glaube ich, dass ein HashSet dieses Problem lösen würde, was ein O (1) Lookup ermöglicht ... Jedoch kann ich keine Hashsets oder Hashtables in der swi-prolog Dokumentation finden.

Gibt es eine Swi-Prolog-Bibliothek für Hashsets, oder kann ich sie irgendwie selbst mit term_hash \ 2 erstellen?

Bonus Info, werde ich höchstwahrscheinlich müssen die auf einigen dynamisch hinzugefügt Daten sehen tun, entweder zu einer Hashset Datenstruktur oder mit assertz

Answer 1

aller schweren Prolog Systeme führen diese O (1) Nachschlagen über Hashing automatisch und implizit für Sie, so dass Sie es nicht selbst tun müssen.

Es heißt Argument-Indexierung, und Sie finden dies in allen guten Prolog Bücher erklärt. Siehe auch "JIT (Just-in-Time) Indizierung" in neueren Versionen vieler Prolog-Systeme, einschließlich SWI. Die Indexierung wird auch auf dynamisch hinzugefügte Klauseln angewendet und ist ein Grund, warum assertz/1 verlangsamt wird und daher keine gute Wahl für Daten ist, die sich häufiger ändern als gelesen werden.

Sie können dies auch einfach selbst testen, indem Sie Datenbanken mit immer mehr Fakten erstellen und sehen, dass die Suchzeit ungefähr konstant bleibt, wenn die Argumentindizierung angewendet wird.

Answer 2

Wenn die Indizierung des ersten Arguments nicht ausreicht (beachten Sie, dass einige Prolog-Systeme auch eine Indizierung mit mehreren Argumenten bieten), können Sie je nach System Ihr eigenes Indexierungsschema mithilfe eines integrierten oder Bibliotheks-Hashings erstellen Prädikat. Im Fall von ECLiPSe, GNU Prolog, SICStus Prolog, SWI-Prolog und YAP, schauen Sie in die Dokumentation des Prädikats term_hash/4.