From: Josef Eschgfaeller
Subject: Equality of hash tables
Date: 
Message-ID: <37A4D67C.1C5BE2FE@felix.unife.it>
Is there some efficient method for comparing hash tables, if
these are allowed to have other hash tables as keys? For example
if one deals with sets - represented as hash tables with :test 'equal -
whose elements can be sets.

I defined the following functions, the non-standard parts having
the obvious meaning. for-every-element-in is a maphash with only
one variable, since the second one is 1 or nil anyway.

The algorithm in sets= makes first a copy of b, from which it
cancels then all elements appearing in a, using the function in,
which refers again to sets=. If there is some element in a,
which is not in b, the algorithm returns nil. If after doing
this, in the copy of b nothing remains, sets= returns t,
otherwise nil. The cases in which not both a and b are sets
are obvious.

  (defun sets= (a b)
    (let ((ha (hash-table-p a)) (hb (hash-table-p b)))
      (cond ((nor ha hb) (equal a b))
      ((and ha hb) (let ((copy-of-b (copy-set b)))
        (for-every-element-in a #'(lambda (x)
          (if (in x b) (remhash x copy-of-b)
            (return-from sets= nil))))
        (= (hash-table-count copy-of-b) 0)))
      (t nil))))

  (defun in (x a)
    (for-every-element-in a #'(lambda (y)
      (if (sets= x y) (return-from in t)))) nil)

Perhaps in full generality it's not an easy problem. If someone
can give bibliographical references, I would be grateful.

Josef Eschgfaeller
Dipartimento Matematico
Universita' di Ferrara
http://felix.unife.it/    Mathematical BBS

From: Pekka P. Pirinen
Subject: Re: Equality of hash tables
Date: 
Message-ID: <ixbtcq6sm9.fsf@gaspode.cam.harlequin.co.uk>
Josef Eschgfaeller <···@felix.unife.it> writes:
> Is there some efficient method for comparing hash tables, if
> these are allowed to have other hash tables as keys? For example
> if one deals with sets - represented as hash tables with :test 'equal -
> whose elements can be sets.

Vassil Nikolov's suggestion of using two SUBSETPs is better, but he's
also right that you need to reconsider what's important about this
data structure.  It would possibly be more efficient to weed out the
duplicates when adding elements to sets:

(defun sets-adjoin (el set)
  (if (hash-table-p el)
      (unless (in el set) (setf (gethash el set) 1))
    (setf (gethash el set) 1))
  set)

And similarly for SETS-UNION etc.  Then SETS= could be simplified.

>   (defun sets= (a b)
>     (let ((ha (hash-table-p a)) (hb (hash-table-p b)))
>       (cond ((nor ha hb) (equal a b))
>       ((and ha hb) (let ((copy-of-b (copy-set b)))
>         (for-every-element-in a #'(lambda (x)
>           (if (in x b) (remhash x copy-of-b)
>             (return-from sets= nil))))
>         (= (hash-table-count copy-of-b) 0)))
>       (t nil))))

(Ouch, your indentation is too tight!)  That has got a bug, in that
REMHASHing X might fail, because it's not EQUAL to an element of
COPY-OF-B, just SETS= to one.  Also, there might be multiple elements
SETS= to X in COPY-OF-B, REMHASH only removes one element.
-- 
Pekka P. Pirinen
Those who do not understand Lisp are doomed to reimplement it.
  - Erik Naggum <erik_naggum.no>
From: Vassil Nikolov
Subject: Re: Equality of hash tables
Date: 
Message-ID: <l03130300b3ca7d94a24a@195.138.129.106>
Josef Eschgfaeller wrote:                [1999-08-01 23:21 +0000]

  > Is there some efficient method for comparing hash tables, if
  > these are allowed to have other hash tables as keys? For example
  > if one deals with sets - represented as hash tables with :test 'equal -
  > whose elements can be sets.

EQUAL is the same as EQL for hash tables, therefore it has limited
usability as the hash table test if the keys can also be hash tables.

Now EQUALP does descend hash tables recursively, so it might (or
might not) be suitable for your purposes.

  > I defined the following functions, the non-standard parts having
  > the obvious meaning. for-every-element-in is a maphash with only
  > one variable, since the second one is 1 or nil anyway.
  > 
  > The algorithm in sets= makes first a copy of b, from which it
  > cancels then all elements appearing in a, using the function in,
  > which refers again to sets=. If there is some element in a,
  > which is not in b, the algorithm returns nil. If after doing
  > this, in the copy of b nothing remains, sets= returns t,
  > otherwise nil. The cases in which not both a and b are sets
  > are obvious.
  [...]

Making a copy seems rather wasteful when just a comparison
is needed.  Why not define the set equality test in terms of
the test for subset, the latter being easily done by a `single
pass' of MAPHASH (or a hash table iterator).


Vassil Nikolov
Permanent forwarding e-mail: ········@poboxes.com
For more: http://www.poboxes.com/vnikolov
  Abaci lignei --- programmatici ferrei.





 Sent via Deja.com http://www.deja.com/
 Share what you know. Learn what you don't.