I'm building a set that contains instances of my-class. I'd like to
use a hash-table, so I can have a quick test whether an element is in
the set. However, I need to consider two instances to be "equal"
[call it my-equal] if they are equalp in all their slots, and so on
recursively. Or more generally, my-equal could be any equivalence
relation implemented as a generic function. I can think of three ways
to do this, but they all seem awkward. Does anyone have suggestions?
One way is to write a method
(defmethod hash-code ((x my-class)) [...])
It would return a symbol or integer for use in an eql hash-table. But
what about collisions? If x is not my-equal to y but (eql (hash-code
x) (hash-code y)), then I'd have to store both x and y under the code.
That is, I'd have to write my own hash bucket code. Buckets within
buckets?
Second, I could require (hash-code x) to be *distinct* for each
distinct x. Mathematically, hash-code would have to be an *injective*
mapping. Then an eql hash-table would work. But for most
applications, hash-code would be hard to write, or slow.
Third, I could require a method
(defmethod hash-key ((x my-class)) [...])
When x my-equals y, we only require the hash-key images to match under
equalp. That is, x my-equals y holds if and only if (equalp (hash-key
x) (hash-key y)). This is still injective, but would be easier to
write. For instance, if my-class has slots a,b,c which equalp knows
how to handle individually, then hash-key could return (vector a b c).
But this approach is also awkward--wasted memory for the vectors, and
updating problems if you try to cache them.
The moral of this post:
I wish equalp were a generic function.
From: Julian Stecklina
Subject: Re: Using CLOS instances in a hash-table
Date:
Message-ID: <86aczy95c1.fsf@web.de>
···············@yahoo.com (Mark McConnell) writes:
> I'm building a set that contains instances of my-class. I'd like to
> use a hash-table, so I can have a quick test whether an element is in
> the set. However, I need to consider two instances to be "equal"
> [call it my-equal] if they are equalp in all their slots, and so on
> recursively. Or more generally, my-equal could be any equivalence
> relation implemented as a generic function. I can think of three ways
> to do this, but they all seem awkward. Does anyone have suggestions?
You could consider using a binary search tree. It would be not as fast
as a well implemented hashtable ( O(log(n)) vs O(n) ), but I guess it
is fast enough for most purposes. The only problem is defining a nice
predicate ...
> I wish equalp were a generic function.
No need to make it slower than it already is. ;) equalp is certainly
useful, but most of the time only in early prototyping.
Regards,
--
Julian Stecklina
Signed and encrypted mail welcome.
Key-Server: pgp.mit.edu Key-ID: 0xD65B2AB5
FA38 DCD3 00EC 97B8 6DD8 D7CC 35D8 8D0E D65B 2AB5
Any sufficiently complicated C or Fortran program
contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
- Greenspun's Tenth Rule of Programming
Julian Stecklina wrote:
> > I wish equalp were a generic function.
>
> No need to make it slower than it already is. ;) equalp is certainly
> useful, but most of the time only in early prototyping.
There's no reason it would have to be any slower if this
were done. After all, it already has to dispatch on the
classes of its arguments. Any customized dispatching logic
could be reused with little change in a user-extensible version.
Paul