Hello,
I am trying to hack out a way to key a hash table pairs of values so
that it can represent a grid with x and y coordinates.
Right now I'm trying to key it with symbols composed of both values,
such as 'X3Y6. This means writing access macros that receive x and y
coordinates, concatenate them into a symbol name, and then attempt to
store values in the hash table based on such composites. This might not
be possible, and is clearly inelegant.
I wanted to check with more experienced programmers to see if there
was a more direct way to do this. For instance, can hash tables be
keyed by strings or lists? I would like to avoid using an array since
it would not be resizable if additional coordinates were needed.
Thanks in advance for any suggestions,
Eric
>>>>> "Eric" == Eric Hsu <···@ai.sri.com> writes:
Eric> Hello, I am trying to hack out a way to key a hash table pairs
Eric> of values so that it can represent a grid with x and y
Eric> coordinates.
This is what I use for two-valued hash tables. I've also got versions
for three- and four-value keys. As I understand it, hash tables are
likely to be suboptimal when the number of keys is small (<60?), so
nested hash-tables might be gratutious, wasteful and not be the best
choice, but isn't it fun? :-)
(defun two-hash (ht-zero key1 key2 &optional (default nil))
(let ((ht-one (gethash key1 ht-zero nil)))
(if ht-one
(gethash key2 ht-one default)
(values default nil))))
(defun (setf two-hash) (value ht-zero key1 key2 &optional (default nil))
(declare (ignore default))
(let ((ht-one (gethash key1 ht-zero
(make-hash-table :test #'equal))))
(setf (gethash key2 ht-one) value)
(setf (gethash key1 ht-zero) ht-one)
value))
(defun two-hash-to-list (ht-zero)
(loop for key1 being each hash-key in ht-zero
append
(let ((ht-one (gethash key1 ht-zero)))
(loop for key2 being each hash-key in ht-one
collect (let ((val (gethash key2 ht-one)))
(append (list key1 key2)
(if (atom val)
(list val)
val)))))))
--
Russell Senior ``The two chiefs turned to each other.
·······@teleport.com Bellison uncorked a flood of horrible
profanity, which, translated meant, `This is
extremely unusual.' ''
Hi,
Russell Senior <·······@teleport.com> writes:
> for three- and four-value keys. As I understand it, hash tables are
> likely to be suboptimal when the number of keys is small (<60?), so
> (defun (setf two-hash) (value ht-zero key1 key2 &optional (default nil))
> (declare (ignore default))
> (let ((ht-one (gethash key1 ht-zero
> (make-hash-table :test #'equal))))
This line creates a new hashtable for every SETF. Just create one
when it's needed. The default argument to GETHASH is "dangerous" and
should only be used on primitive values or variables, not
constructors. Use the second return value of GETHASH to check for the
different cases. It will make your code look more complicated,
though. But you can read Paul Graham's "On Lisp" and hide the
complexity in good looking macro invocations.
> (defun two-hash-to-list (ht-zero)
> (loop for key1 being each hash-key in ht-zero
> append
> (let ((ht-one (gethash key1 ht-zero)))
> (loop for key2 being each hash-key in ht-one
> collect (let ((val (gethash key2 ht-one)))
> (append (list key1 key2)
Here the COLLECT or COLLECTING macros recently posted (by Tim
Bradshaw, Sam Steingold and Bruno Haible among others) will help
collecting from within nested loops instead of wasteful APPENDs. Your
code will even look much cleaner. (collectors appended)
Another comment: MAPHASH gives you you both key and value so you don't
need to call (gethash key1 ht-zero).
Or you can still use LOOP on hash-tables but make use of the USING
keyword to give you both key and value in one pass. The HyperSpec:
for-as-hash::= var [type-spec] being {each | the}
{{hash-key | hash-keys} {in | of} hash-table
[using (hash-value other-var)] |
{hash-value | hash-values} {in | of} hash-table
[using (hash-key other-var)]}
Enjoy sharing code,
J"org H"ohle
Forschungszentrum Telekom AG/Telekom Research Center
From: Tim Bradshaw <···@aiai.ed.ac.uk>
Newsgroups: comp.lang.lisp
Subject: Re: Append object to list - Question
Date: 05 Oct 1998 12:25:37 +0100
Organization: AIAI, University of Edinburgh
Lines: 37
Message-ID: <···············@wiay.aiai.ed.ac.uk>
References: <··························@ts03-038.dublin.indigo.ie>
<·················@genworks.com>
X-Trace: scotsman.ed.ac.uk 907586715 4144 129.215.105.39 (5 Oct 1998 11:25:15 GMT)
X-Complaints-To: ······@scotsman.ed.ac.uk
NNTP-Posting-Date: 5 Oct 1998 11:25:15 GMT
X-Newsreader: Gnus v5.2.25/XEmacs 19.14
* David J Cooper wrote:
> 1. When I am building up a list inside some kind of loop (e.g. a property
> list), I often use push, then nreverse the final result, a technique used
> often by Graham in ANSI Common Lisp:
I tend to use this thing, that I wrote, but stole I'm sure from
somewhere else (possibly Interlisp?). It probably needs to be
generalised somehow, not to mention cleaned up (all those dollar
signs...), but it's quite useful, especially if you want to collect
things over several loops or something.
(defmacro collecting (&body forms)
;; Collect some random stuff into a list by keeping a tail-pointer
;; to it, return the collected list. No real point in using
;; gensyms, although one probably should on principle.
"Collect things into a list forwards. Within the body of this macro
The form `(COLLECT THING)' will collect THING into the list returned by
COLLECTING. Uses a tail pointer -> efficient."
(let (($resnam$ (gensym)) ($tail$ (gensym)) ($thing$ (gensym)))
`(let
(,$resnam$ ,$tail$)
(macrolet
((collect
(thing)
;; Collect returns the thing it's collecting
`(let ((,',$thing$ ,thing))
(if ,',$resnam$
(setf (cdr ,',$tail$)
(setf ,',$tail$ (list ,',$thing$)))
(setf ,',$resnam$
(setf ,',$tail$ (list ,',$thing$))))
,',$thing$)))
,@forms)
,$resnam$)))
--tim
From: Sam Steingold <···@goems.com>
Newsgroups: comp.lang.lisp
Subject: Re: Collecting/LOOP (was Re: Please help)
Date: 09 Apr 1999 17:37:51 -0400
Organization: disorganization
Lines: 86
Message-ID: <··············@eho.eaglets.com>
References: <···························@ppnorn.atlant.ru> <···················@news.rdc1.bc.wave.home.com> <··············@copernico.parades.rm.cnr.it> <··············@foobar.orion.no> <············@nnrp1.dejanews.com> <··············@g.pet.cam.ac.uk> <············@nnrp1.dejanews.com> <···············@world.std.com> <············@nnrp1.dejanews.com> <··············@localhost.localdomain> <·················@computer.org> <···············@tfeb.org> <························@meta.Tesserae.COM> <·················@IntelliMarket.Com> <··············@Pacific.AI.SRI.COM> <·············@res.raytheon.com> <···············@lostwithiel.tfeb.org>
Reply-To: ···@goems.com
X-Trace: ffx2nh5.news.uu.net 923693873 29146 208.235.77.238 (9 Apr 1999 21:37:53 GMT)
X-Complaints-To: ····@ffx2nh5.news.uu.net
NNTP-Posting-Date: 9 Apr 1999 21:37:53 GMT
Return-Receipt-To: ···@goems.com
X-Disclaimer: You should not expect anyone to agree with me.
X-Attribution: Sam
X-Newsreader: Gnus v5.7/Emacs 20.3
>>>> In message <···············@lostwithiel.tfeb.org>
>>>> On the subject of "Re: Collecting/LOOP (was Re: Please help)"
>>>> Sent on 09 Apr 1999 21:15:46 +0100
>>>> Honorable Tim Bradshaw <···@tfeb.org> writes:
>>
>> Well, judging by the C/C++ example, Lisp will never take over the
>> world if people don't spend vast amounts of time micro-optimising
>> their programs. So this is definitely to be encouraged!
(-: I tried the following:-)
(defmacro collecting-tail (&body forms)
(let ((ret (gensym "COLLECTING")) (tail (gensym "COLLECTING")))
`(let ((,ret nil) (,tail nil))
(macrolet ((collect (form)
`(if ,',ret
(setf (cdr ,',tail) (setf ,',tail (list ,form)))
(setf ,',ret (setf ,',tail (list ,form))))))
,@forms
,ret))))
(defmacro collecting-nreverse (&body forms)
(let ((ret (gensym "COLLECTING")))
`(let ((,ret nil))
(macrolet ((collect (form) `(push ,form ,',ret)))
,@forms
(nreverse ,ret)))))
(defun test-collect (which &optional (nn 1000000) (kk 10))
(flet ((ts ()
(let ((bt (get-internal-run-time)) time)
(ecase which
(:nreverse (collecting-nreverse (dotimes (i nn) (collect i))))
(:tail (collecting-tail (dotimes (i nn) (collect i)))))
(setq time (/ (- (get-internal-run-time) bt)
internal-time-units-per-second))
(format t "~&~a:~10t~10f~%" which time)
#+clisp (lisp:gc) #+allegro (excl:gc) #-(or clisp allegro) (gc)
time)))
(mean (loop :for ii :from 1 :to kk :collect (ts)))))
(test-collect :tail)
(test-collect :nreverse)
for ACL, `collecting-tail' is twice as fast as `collecting-nreverse',
for CMUCL, `collecting-tail' is 1.5 times as fast as `collecting-nreverse',
for CLISP, `collecting-nreverse' is 1.25 times as fast as `collecting-tail'.
In all 3 cases the absolute difference seems negligible compared to
memory allocation and garbage collection, so I don't think this really
matters - just like it was mentioned many times already by others. :-)
But if you are really into it, you might want to use this:
(defmacro with-collect ((&rest collectors) &body forms)
"Evaluate forms, collecting objects into lists.
Within the FORMS, you can use local macros listed among collectors,
they are returned as multiple values.
E.g., (with-collect (c1 c2) (dotimes (i 10) (if (oddp i) (c1 i) (c2 i))))
==> (1 3 5 7 9); (0 2 4 6 8) [2 values]
In CLISP, push/nreverse is about 1.25 times as fast as pushing into the
tail, so this macro uses push/nreverse on CLISP and push into the tail
on other lisps (which is 1.5-2 times as fast as push/nreverse there)."
(let ((ret (mapcar (lambda (cc) (gensym (format nil ···@(~s~)-RET-" cc)))
collectors))
#-clisp
(tail (mapcar (lambda (cc) (gensym (format nil ···@(~s~)-TAIL-" cc)))
collectors)))
`(let (,@ret #-clisp ,@tail)
(macrolet ,(mapcar (lambda (co re #-clisp ta)
`(,co (form)
#+clisp `(push ,form ,',re)
#-clisp
`(if ,',re
(setf (cdr ,',ta) (setf ,',ta (list ,form)))
(setf ,',re (setf ,',ta (list ,form))))))
collectors ret #-clisp tail)
,@forms
(values #+clisp ,@(mapcar (lambda (re) `(nreverse ,re)) ret)
#-clisp ,@ret)))))
--
Sam Steingold (http://www.goems.com/~sds) running RedHat5.2 GNU/Linux
Micros**t is not the answer. Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
Bus error -- please leave by the rear door.
>>>>> "me" == Russell Senior <·······@teleport.com> writes:
>>>>> "JCH" == Joerg-Cyril Hoehle <············@tzd.dont.telekom.spam.de.me> writes:
me> (defun (setf two-hash) (value ht-zero key1 key2 &optional (default
me> nil)) (declare (ignore default)) (let ((ht-one (gethash key1
me> ht-zero (make-hash-table :test #'equal))))
JCH> This line creates a new hashtable for every SETF. Just create
JCH> one when it's needed. The default argument to GETHASH is
JCH> "dangerous" and should only be used on primitive values or
JCH> variables, not constructors. [... other helpful comments snipped]
I haven't tried using the COLLECTING macro stuff yet, but I did try
removing some of the more egregious consing. Here is my current
two-hash version:
(defun two-hash (ht-zero key1 key2 &optional (default nil))
(let ((ht-one (gethash key1 ht-zero nil)))
(if ht-one
(gethash key2 ht-one default)
(values default nil))))
(defun (setf two-hash) (value ht-zero key1 key2 &optional (default nil))
(declare (ignore default))
(multiple-value-bind (ht-one present-p)
(gethash key1 ht-zero)
(unless present-p
(setq ht-one (setf (gethash key1 ht-zero)
(make-hash-table :test #'equal))))
(setf (gethash key2 ht-one) value)
value))
(defun two-hash-to-list (ht-zero)
(loop for key1 being each hash-key in ht-zero
using (hash-value ht-one)
nconc
(loop for key2 being each hash-key in ht-one
using (hash-value val)
collect (if (atom val)
(list key1 key2 val)
(list* key1 key2 val)))
))
--
Russell Senior ``The two chiefs turned to each other.
·······@teleport.com Bellison uncorked a flood of horrible
profanity, which, translated meant, `This is
extremely unusual.' ''
* Eric Hsu wrote:
> I would like to avoid using an array since
> it would not be resizable if additional coordinates were needed.
Arrays in CL can be (optionally) resized. A hashtable approach is
only really useful if your arrays are rather sparse.
--tim
In article <·················@ai.sri.com>, Eric Hsu <···@ai.sri.com> wrote:
> Hello,
>
> I am trying to hack out a way to key a hash table pairs of values so
> that it can represent a grid with x and y coordinates.
Can't you just use complex numbers as keys?
(setf t1 (make-hash-table))
(setf (gethash #c(2 3) t1) 'a)
> be possible, and is clearly inelegant.
> I wanted to check with more experienced programmers to see if there
> was a more direct way to do this. For instance, can hash tables be
> keyed by strings or lists?
You can specify the kind of hashtable you want to use:
(make-hash-table :test #'equalp)
Or you can write your own hash-function.
> I would like to avoid using an array since
> it would not be resizable if additional coordinates were needed.
You can create adjustable arrays.
Anyway, you need to read the docs about
MAKE-HASH-TABLE :
http://www.harlequin.com/education/books/HyperSpec/Body/fun_make-hash-table.html
······@lavielle.com (Rainer Joswig) writes:
>
> In article <·················@ai.sri.com>, Eric Hsu <···@ai.sri.com> wrote:
> > I am trying to hack out a way to key a hash table pairs of values so
> > that it can represent a grid with x and y coordinates.
>
> Can't you just use complex numbers as keys?
>
> (setf t1 (make-hash-table))
> (setf (gethash #c(2 3) t1) 'a)
This looks pretty clever.
> > be possible, and is clearly inelegant.
> > I wanted to check with more experienced programmers to see if there
> > was a more direct way to do this. For instance, can hash tables be
> > keyed by strings or lists?
>
> You can specify the kind of hashtable you want to use:
>
> (make-hash-table :test #'equalp)
At least on some systems, the performance of EQUAL hash tables is much,
much worse than EQL hash tables. That might be a reason to go for the
complex number approach. It would perhaps be a bit simpler than
cascading hash tables.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
Thomas A. Russ wrote:
> ······@lavielle.com (Rainer Joswig) writes:
>
> >
> > In article <·················@ai.sri.com>, Eric Hsu <···@ai.sri.com> wrote:
> > > I am trying to hack out a way to key a hash table pairs of values so
> > > that it can represent a grid with x and y coordinates.
> >
> > Can't you just use complex numbers as keys?
> >
> > (setf t1 (make-hash-table))
> > (setf (gethash #c(2 3) t1) 'a)
>
> This looks pretty clever.
>
> > > be possible, and is clearly inelegant.
> > > I wanted to check with more experienced programmers to see if there
> > > was a more direct way to do this. For instance, can hash tables be
> > > keyed by strings or lists?
> >
> > You can specify the kind of hashtable you want to use:
> >
> > (make-hash-table :test #'equalp)
>
> At least on some systems, the performance of EQUAL hash tables is much,
> much worse than EQL hash tables. That might be a reason to go for the
> complex number approach. It would perhaps be a bit simpler than
> cascading hash tables.
>
True. One should always be concerned with performance, but functionality must
come first. I populate several EQUAL hash-tables with 12,000 elements or more
with an imperceivable cost in performance compared to an equivalent collection
of tables keyed to some integer value. The benefit in data retrieval in using
EQUAL has been tremendous for me, but I believe that the Lisp implementation and
platform play a role in its viability.
> --
> Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
In article <·······················@194.163.195.67>,
Rainer Joswig <······@lavielle.com> wrote:
>In article <·················@ai.sri.com>, Eric Hsu <···@ai.sri.com> wrote:
>> I wanted to check with more experienced programmers to see if there
>> was a more direct way to do this. For instance, can hash tables be
>> keyed by strings or lists?
>
>You can specify the kind of hashtable you want to use:
>
>(make-hash-table :test #'equalp)
For conses or lists where the leaves are all numbers (as they would in this
case), an EQUAL hash table would be appropriate.
>Or you can write your own hash-function.
That's not standard, although it's a common extension, unless you mean that
you write your own hash table implementation to go along with the hash
function.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, 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.
For a while I had this same need. It was a graphics application where
the (x,y) integer pairs were not widely scattered. I converted them to
a single integer with (setq intkey (+ x (* y 100000)). That way I could
use an #'eq hash table and integer keys. Very fast. To key your
original (x,y) back use (setq y (round intkey 100000) x (- intkey (* y
100000)).
--
John Watton
Alcoa Inc.
Sent via Deja.com http://www.deja.com/
Before you buy.
<···········@alcoa.com> wrote in message ·················@nnrp1.deja.com...
> For a while I had this same need. It was a graphics application where
> the (x,y) integer pairs were not widely scattered. I converted them to
> a single integer with (setq intkey (+ x (* y 100000)). That way I could
> use an #'eq hash table and integer keys. Very fast. To key your
> original (x,y) back use (setq y (round intkey 100000) x (- intkey (* y
> 100000)).
#'round gives you both values there is no need to add the second
computation.
It works also with negative values:
CL-USER 8 > (round (+ 1200000 23) 100000)
12
23
CL-USER 9 > (round (+ 1200000 -23) 100000)
12
-23
CL-USER 10 > (round (+ -1200000 23) 100000)
-12
23
CL-USER 11 > (round (+ -1200000 -23) 100000)
-12
-23
Marc Battyani