Pascal Bourguignon <pjb@informatimago.com> wrote:
+---------------
| akopa <akopa.gmane.poster@gmail.com> writes:
|
| > Does anyone have any insight into which is more efficient when the
| > number of elements in the sequence keys is constant? E.g. (gethash
| > '(foo bar) hash) vs (gethash 'bar (gethash 'foo hash)). I have a
| > function I want to memoize on a certain number of arguments, but I
| > don't to cons up a list (or vector) every time I check the table.
|
| This is totally implementation dependant. If you really care, you
| should profile it.
+---------------
In addition, some implementations do a *MUCH* better or worse
job of hashing some data types than others. In <akopa>'s case,
the types to compare are conses (and/or lists and/or trees)
versus symbols. [I only mention this because in the past some
versions of some implementations were known to have very bad
hashing performance on conses.]
Also note that if you "cons up a list" to compute a hash key
at runtime, you *must* use an EQUAL or EQUALP hash table
(since your freshly-consed keys will never be EQ or EQV
to any already-existing entry), which is potentially more
expensive, whereas with nested hash tables with symbols
as keys EQ hash tables will always suffice. [The "Subject:"
<akopa> used implies that was already known, but I thought
I'd mention it "pour les autres".]
On the other hand, nested hash tables have a memory cost,
so it depends.
As Pascal suggests, if it really matters then profile it.
-Rob
p.s. I'd also suggest reading the section in the CLHS on SXHASH
and following the references to the material on "similarity",
especially the implications of objects which are not EQUAL or
EQUALP but *are* "similar" [that is, they'll have the same SXHASH
value and thus GETHASH for such keys may have to traverse long
internal lists of hash table entries with the same hash value
until it finds the one that's EQUAL/EQUALP to the GETHASH key arg].
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607