RE: Hash Table

[Paul Leader]

For the bahaviour of assert[az] (there is no assert predicate, my mistake)
and retract see 
http://gnu-prolog.inria.fr/manual/manual029.html

The solution I presented could be better refered to as an associated array,
it associates an object with some index value.  The calulation of the index
value is totally dependent on the kind of information that you want to store
and retrieve.  A hash-table is simply an associative array, with the hash
function used to generate the index.  How you use these depends on the
application that you are creating.

One use for such a system in prolog is where you have a complex structure
based on either large or nested functors.  e.g.
        foo(bar(x,y), rep(t,y,u,i,o,p), con(bar2(q), r))

Now you might want to store many of these structures and retrieve them based
on only partial information, for example the values of y, p, and q.  Lets
say you wanted to return all the clauses where y, p and r are 1,2 and 3
respectively, you could do the following.  This would result in a linear
search of all (or at least most) of the clauses of the form foo/3.  This
would be very slow.

        :- foo(bar(X,1), rep(T,1,U,I,O,2), con(bar2(3), R)).

If y, p, and q were always going to be used as the index you could use the
hash-table stucture that has been given to store the strucures

store_foo(foo(bar(_X, Y), rep(_T, Y, _U, _I, _O, P), con(bar2(Q), _R)) :-
        generate_hash(Y, P, Q, Hash_Val),
        insert(Hash_Val, foo(bar(_X, Y), rep(_T, Y, _U, _I, _O, P),
con(bar2(Q), _R)).

If you want, the hash value could be returned as a third argument of
store_foo.

To retrieve the item the hash simply needs to be regenerated from the values
of Y, P and Q.  By backtracking, all items with the same hash will be
returned, and a linear search conducted of them, either with a failure
driven loop, or using the findall/3 predicate.  Of course the trick with
hash tables is to minimise the number of items that share the same hash
value, thus minimising the use of linear searches.  In imperative
programming this is normally balanced against the desire to save space, but
since this strucure in prolog does not lead to wasted space, this isn't an
issue.

At the moment I'm not in a position to try this approach out compiled by
GNU-Prolog, but the manual gives no indication that it should not work, and
it works fine in poplog.  When I have re-installed gnuprolog I shall give it
a try and see how the performance compairs.  The performace difference
between a linear search of the database buy unification with each clause in
turn, and index guided unification via the first argument-primary functor
indexing, is normally an order of magnitude.  The first grows linearly with
the number of clauses to search ( O(N) ), while the latter is almost
constant time ( O(1) )

Paul

> -----Original Message-----
> From: Hector Luis Palacios V. [mailto:address@hidden
> Sent: 01 October 2001 15:27
> To: Paul Leader
> Cc: address@hidden
> Subject: RE: Hash Table
> 
> 
> 
> Paul, you gave us a solution to that, but what happend
> with "assert" and "retract" in compile code?
> How about the performance??
> 
> A reason to have a hash table may be the specific hash function
> that you want to use, by example.
> So, I still interested in the question about the table.
> 
> 
> On Mon, 1 Oct 2001, Paul Leader wrote:
> 
> > I'm intregued as to why you would want a hash table in Prolog.
> > ............
> > insert(Index, Item) :- assert(hash_item(Index, Object)).
> > 
> > retrieve(Index, Item) :- hash_item(Index, Object).
> > ................
> > 
> > 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
> > 
> 
> 
> Hector Palacios
> 


**********************************************************************
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.

www.praxis-cs.co.uk
**********************************************************************