[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: Hash Table

From: Paul Leader
Subject: RE: Hash Table
Date: Mon, 1 Oct 2001 09:53:57 +0100

I'm intregued as to why you would want a hash table in Prolog.

If you just want a means of storing data in a manner that is fast to
retrieve then you can exploit the facilities of prolog.

Prolog normally indexes all terms in the database based on the primary
functor of the first argument of the head of the clause.  Therefore if the
first term of the predicate is the index for the item, then it will be
automatically indexed.

for example
        evaluate(A, B, <=):- ...
        evaluate(A, B, <) :- ...

:- evaluate(1,2,<).

Prolog will attempt to unify against both clauses, backtracking as it goes.

        evaluate(<=, A, B) :-...
        evaluate(<, A, B) :-...

:- evaluate(<, 1, 2).

Prolog will jump straight to the second clause because of the indexing.

This is a useful trick to use in all of your programming, but is obviously
most usefull where you have many clauses of the same predicate.  How the
indexing is done will be implementation dependent, but it generally give a
performance boost in orders of magnitude over linear searching.

To use it to build a hash table (of sorts)

insert(Index, Item) :- assert(hash_item(Index, Object)).

retrieve(Index, Item) :- hash_item(Index, Object).

delete(Index, Object) :- retract(hash_item(Index, Object)).

delete(index) :- retractall(hash_item(Index, _AnyObject)).

deleteall :- retractall(hash_item(_Index, _Object)).

The assert/1 predicate asserts a term into the database as a fact (also
check out assertz and assertz).  The insert predicate here will assert
hash_item/2 terms into the database.  The retrieve predicate will then use
the indexing described above to retrieve the item in a very short time.

If there is a clash of index then there will be two clauses with the same
index.  This is not a problem, prolog will simply backtrack over them,
unless you use a cut and have it only return the first.

To delete items you use the retract and retractall predicates.  These will
remove a clause from the database.  Here I have given three ways of useing
them.  In the first case the exact entry is retracted.  In the second all
items with the index value associated with them are retracted.  In the
third, all hash_item clauses are retracted (i.e. the hash table is
completely removed).

Hope this helps.  Indexing, like difference lists is a trick that can really
improve the preformance of a Prolog program and is worth using.

The best thing to do is try it out and time it to see if the speed
difference is worth the work.

Paul Leader

-----Original Message-----
From: The BenJamin [mailto:address@hidden
Sent: 30 September 2001 04:31
To: address@hidden
Subject: Hash Table

I was wondering if anyone could help me out as I have to implement a hash
table in prolog. I am currently having a lot of trouble doing it at the
moment and was wondering if anyone could help me out or give me some

Thanks Ben

This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are addressed. If you have received this email in error please notify
the system manager.

This footnote also confirms that this email message has been swept 
for the presence of computer viruses.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]