Hello,
I've written a small program, which as part of its processing stores a fair
number of hashtable entries in one hashtable (close to 200000). What I have
tried so far uses (make-hash-table :test 'equalp), since the keys in this
case are vectors of integers, basically calculated from the values in each
entry, so that I can essentially map backwards again.
i.e. the key is #(1 0 4 0 5 0), calculated from a specific value. I want to
be able to modify vectors like this, then check to see if THAT vector is in
the hashtable.
Anyway, it does happen to work, but profiling in CMUCL shows that nearly all
the work is happening in my gethash calls. Fair enough, I realize that it's
expensive compared to simpler hash keys, but what might be a better way to
do this?
Thanks,
Tim
From: Bulent Murtezaoglu
Subject: Re: hashtable suggestions (or perhaps a different approach?)
Date:
Message-ID: <87664pi53n.fsf@nkapi.internal>
>>>>> "TL" == Tim Lavoie <········@spamcop.net> writes:
[...]
TL> Anyway, it does happen to work, but profiling in CMUCL shows
TL> that nearly all the work is happening in my gethash
TL> calls. Fair enough, I realize that it's expensive compared to
TL> simpler hash keys, but what might be a better way to do this?
A quick hack I used when I was doing the ITA addagram problem was to
turn my vectors of integers into strings. Strings can be used with
equal hash tables, and if your integers are in the 0-255 range the
conversion is straightforward and fast (for CMUCL, YMMV with other
lisps). Equal hashtables are faster than equalp hashtables. This is
not a general solution, though.
Here's what found (AFAIR, my arrays were 26 element long representing
words in a transform domain by letter counts)
(declaim (inline tostring))
(defun tostring (a)
(let ((str (make-string 26)))
(dotimes (i 25)
(setf (aref str i) (code-char (aref a i))))
str))
if you are just looking things up and not storing anything in the hash table
you probably want to pull that let outside the defun and have a 'static'
buffer to avoid consing on every call.
cheers,
BM
From: Erik Naggum
Subject: Re: hashtable suggestions (or perhaps a different approach?)
Date:
Message-ID: <3223403910932466@naggum.net>
* Tim Lavoie <········@spamcop.net>
| Anyway, it does happen to work, but profiling in CMUCL shows that nearly
| all the work is happening in my gethash calls. Fair enough, I realize
| that it's expensive compared to simpler hash keys, but what might be a
| better way to do this?
It could be that all the keys wind up in the same hash bucket. You have
to inspect the hash table internals to see if this is the case or not,
but the documentation might also provide important clues.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
In article <················@naggum.net>, Erik Naggum wrote:
>
> It could be that all the keys wind up in the same hash bucket. You have
> to inspect the hash table internals to see if this is the case or not,
> but the documentation might also provide important clues.
Thanks Erik (and Bulent too)
I'll try both your suggestions out and see how that goes. One thing which
seemed curious is that the same code was dramatically faster in CLISP than
CMUCL, but as you say, the hash table internals may be informative here. In
any case, It's something of a learning experience either way; I get to poke
around under the hood to see how things work, and learn to write better code
which doesn't depend so much on specific implementation quirks.
Cheers,
Tim
From: Arseny Slobodjuck
Subject: Re: hashtable suggestions (or perhaps a different approach?)
Date:
Message-ID: <3c776265.662252@news.vtc.ru>
On Fri, 22 Feb 2002 21:03:32 GMT, Tim Lavoie <········@spamcop.net>
wrote:
>i.e. the key is #(1 0 4 0 5 0), calculated from a specific value.
Why not use 104050 ? Lisp supports much longer integers.
You may have integer-key-to-list and list-to-integer-key functions
for converting.
In article <···············@news.vtc.ru>, Arseny Slobodjuck wrote:
> On Fri, 22 Feb 2002 21:03:32 GMT, Tim Lavoie <········@spamcop.net>
> wrote:
>
>>i.e. the key is #(1 0 4 0 5 0), calculated from a specific value.
> Why not use 104050 ? Lisp supports much longer integers.
> You may have integer-key-to-list and list-to-integer-key functions
> for converting.
Hm. OK, I'll have a look around, thanks.
Tim
--
"In real life, of course, it is the hare who wins. Every time. Look
around you. And in any case, it is my contention that Aesop was
writing for the tortoise market."
--Anita Brookner
From: Matthieu Villeneuve
Subject: Re: hashtable suggestions (or perhaps a different approach?)
Date:
Message-ID: <3C7C3344.246A8617@tumbleweed.com>
Tim Lavoie wrote:
>
> In article <···············@news.vtc.ru>, Arseny Slobodjuck wrote:
> > On Fri, 22 Feb 2002 21:03:32 GMT, Tim Lavoie <········@spamcop.net>
> > wrote:
> >
> >>i.e. the key is #(1 0 4 0 5 0), calculated from a specific value.
> > Why not use 104050 ? Lisp supports much longer integers.
> > You may have integer-key-to-list and list-to-integer-key functions
> > for converting.
How would integer-key-to-list work? I don't see any way to implement
that except if you can guarantee that all your integers are 1-digit
numbers...
--Matthieu
>
> Hm. OK, I'll have a look around, thanks.
>
> Tim
>
> --
> "In real life, of course, it is the hare who wins. Every time. Look
> around you. And in any case, it is my contention that Aesop was
> writing for the tortoise market."
> --Anita Brookner
In article <·················@tumbleweed.com>,
Matthieu Villeneuve <···················@tumbleweed.com> wrote:
>Tim Lavoie wrote:
>>
>> In article <···············@news.vtc.ru>, Arseny Slobodjuck wrote:
>> > On Fri, 22 Feb 2002 21:03:32 GMT, Tim Lavoie <········@spamcop.net>
>> > wrote:
>> >
>> >>i.e. the key is #(1 0 4 0 5 0), calculated from a specific value.
>> > Why not use 104050 ? Lisp supports much longer integers.
>> > You may have integer-key-to-list and list-to-integer-key functions
>> > for converting.
>
>How would integer-key-to-list work? I don't see any way to implement
>that except if you can guarantee that all your integers are 1-digit
>numbers...
They don't have to be 1-digit numbers, but they would all have to be within
a bounded range. Use the size of that range as the "radix" in
list-to-integer-key and integer-key-to-list.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Pierpaolo BERNARDI
Subject: Re: hashtable suggestions (or perhaps a different approach?)
Date:
Message-ID: <olOd8.9025$Ns4.383987@news2.tin.it>
"Tim Lavoie" <········@spamcop.net> ha scritto nel messaggio
···························@news1.mts.net...
> i.e. the key is #(1 0 4 0 5 0), calculated from a specific value. I want
to
> be able to modify vectors like this, then check to see if THAT vector is
in
> the hashtable.
Be sure that you are not modifying the same vectors that you have
used as keys.
If you insert a vector as a key in a hash-table, and then you modify
that vector, you'll make a mess of the table
(see 18.1.2 in the HyperSpec).
P.