On Wed, Nov 24, 2004 at 08:58:25PM +0000, Christophe Rhodes wrote:
> Joseph Kiniry <kiniry@...> writes:
> > On 24 Nov, 2004, at 17:30, Christophe Rhodes wrote:
> >> Would it be appropriate to suggest SB-INT:PSXHASH? Values might not
> >> be the same across sessions, but otherwise it seems to me that hash
> >> values could generate a good approximation to a total order.
> > That is actually a very interesting idea. This would only work though
> > if hash orders were guaranteed consistent across garbage collections...
> PSXHASH is an (SBCL-internal) function for EQUALP hashing, which must
> preserve the hash value for structures across garbage collections
> (since two structures which are EQUALP but with different addresses
> must hash to the same value, the address of the structure cannot
> affect the hash calculation). For standard-objects, there is no such
> guarantee, I think, but I'd be very surprised if any implementation
> rehashed all hash tables containing clos objects after GCs --
> certainly you're safe in SBCL's case.
If you're only hashing a modest number of instances, and you want to
avoid writing more than half a dozen lines of code, this could easily
be your best bet. (I have done it, and been satisfied.) But if you
want to get good performance on messy nested data structures, and if
you know something useful about the properties of your data
structures, it might be pretty easy to do a lot better. For example, I
have, in a program of mine, a problem which seems to be described
exactly by your question. In my version of the problem, I happen to
know that the data structure is a directed acyclic graph, so it's easy
to compute a hash effectively. (Also, as it happens, I have just put
up a preprint of a paper which could be thought of as covering more
cases.:-) I also happen to know that it's pretty common for instances
to share enough substructure that PSXHASH (which only wants to flood
to a fixed depth) could return the same value for many instances.
Thus, it was easy to write a custom hashing operation which won big
compared to PSXHASH.
William Harold Newman <william.newman@...>
"Smart people believe weird things because they are skilled at
defending beliefs they arrived at for nonsmart reasons."
-- Michael Shermer, Sept. 2002 Scientific American