I was just writing a couple of functions for converting from hash to
alist and vice versa.
I'm wondering what to name these functions. Is it customary to use
"hash-to-alist" or "alist-from-hash" or something else?
Stig Hemmer,
Jack of a Few Trades. perl -e 'print "Not a Perl hacker.\n"'
Stig Hemmer wrote:
>
> I was just writing a couple of functions for converting from hash to
> alist and vice versa.
>
> I'm wondering what to name these functions. Is it customary to use
> "hash-to-alist" or "alist-from-hash" or something else?
>
You could get cute and name them hash2alist and alist2hash
David Cooper wrote in message <·················@genworks.com>...
>Stig Hemmer wrote:
>>
>> I was just writing a couple of functions for converting from hash to
>> alist and vice versa.
>>
>> I'm wondering what to name these functions. Is it customary to use
>> "hash-to-alist" or "alist-from-hash" or something else?
>>
>
>You could get cute and name them hash2alist and alist2hash
Cute would be hash->alist, like in Scheme.
"Vassili Bykov" <·······@objectpeople.com> writes:
> David Cooper wrote in message <·················@genworks.com>...
> >Stig Hemmer wrote:
> >>
> >> I was just writing a couple of functions for converting from hash to
> >> alist and vice versa.
> >>
> >> I'm wondering what to name these functions. Is it customary to use
> >> "hash-to-alist" or "alist-from-hash" or something else?
> >>
> >
> >You could get cute and name them hash2alist and alist2hash
>
> Cute would be hash->alist, like in Scheme.
>
Nope! The '->' is not CL style. 'alist-to-hash-table' and
'hash-table-to-alist' seem more sensible.
;;; Just a start...
(defun alist-to-hash-table (alist &key (test #'eql))
(let ((new-ht (make-hash-table :test test)))
(loop for assoc in alist
do (setf (gethash (car assoc) new-ht) (cdr assoc)))
new-ht))
(defun hash-table-to-alist (ht)
(let ((new-alist ()))
(loop for k being each hash-key in ht
do (setf new-alist (acons k (gethash k ht) new-alist)))
new-alist))
;;; The USING clause does not work well in CMUCL.
Cheers
The Code Police
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 10 03 17, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
Marco Antoniotti <·······@copernico.parades.rm.cnr.it> writes:
> (defun alist-to-hash-table (alist &key (test #'eql))
> (let ((new-ht (make-hash-table :test test)))
> (loop for assoc in alist
> do (setf (gethash (car assoc) new-ht) (cdr assoc)))
> new-ht))
>
> (defun hash-table-to-alist (ht)
> (let ((new-alist ()))
> (loop for k being each hash-key in ht
> do (setf new-alist (acons k (gethash k ht) new-alist)))
> new-alist))
>
> ;;; The USING clause does not work well in CMUCL.
For comparison, my own code:
(defun alist-to-hash (alist)
"Returns a hash with same key/value pairs as argument ALIST\
Note that the ALIST shouldn't have duplicate keys."
(let ((result (make-hash-table)))
(loop for (key . value) in alist
do (setf (gethash key result) value))
result))
(defun hash-to-alist (hash)
"Returns an alist with same key/value pairs as argument HASH."
(loop for key being each hash-key in hash
collect (cons key (gethash key hash))))
Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
Jack of a Few Trades.
"Just when you accept that life's a bitch, it has puppies."
Stig Hemmer <····@pvv.ntnu.no> writes:
> For comparison, my own code:
>
> (defun alist-to-hash (alist)
> "Returns a hash with same key/value pairs as argument ALIST\
> Note that the ALIST shouldn't have duplicate keys."
> (let ((result (make-hash-table)))
> (loop for (key . value) in alist
> do (setf (gethash key result) value))
> result))
>
> (defun hash-to-alist (hash)
> "Returns an alist with same key/value pairs as argument HASH."
> (loop for key being each hash-key in hash
> collect (cons key (gethash key hash))))
>
> Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
> Jack of a Few Trades.
> "Just when you accept that life's a bitch, it has puppies."
I was just wondering; why the need to convert between hash tables and
alists? Is there some interface that you are using that requires alists?
If so, then ignore the rest of this post; there's little you can do
about hard requirements. But if you are able to work with hash-tables,
they tend to be much more efficient than alists, and converting back and
forth between the two representations will inevitably cause consing.
For hash-tables, you can use GETHASH and its inverse as accessors, and
MAPHASH for iteration. Or you can just do the iterations using the loop
construct as you have in your hash-to-alist converter, above. The only
thing alists give you over hash tables is a specified ordering, which it
seems that you don't care about, judging from your conversion function.
Perhaps you could tell us what you are using these conversions for, so
we can understand better what your requirements are.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <·············@beta.franz.com>,
Duane Rettig <·····@franz.com> writes:
> If so, then ignore the rest of this post; there's little you can do
> about hard requirements. But if you are able to work with hash-tables,
> they tend to be much more efficient than alists,
Ah, not necessarily so. Years ago when I was on loan to MCC, we did some
checking. On LMI's, the break even point (speedwise) between alists and hash
tables was at 7 elements. On the Symbolics, it was something like 12. That
meant that if you had fewer than 7 elements in your "table", an alist was
faster. If more than 12, then the hashtable was faster. In between, it
depends. It'd be interesting to know what the break even point is for the
various CL implementations.
Mike McDonald
·······@mikemac.com
·······@mikemac.com (Mike McDonald) writes:
> In article <·············@beta.franz.com>,
> Duane Rettig <·····@franz.com> writes:
>
> > If so, then ignore the rest of this post; there's little you can do
> > about hard requirements. But if you are able to work with hash-tables,
> > they tend to be much more efficient than alists,
>
> Ah, not necessarily so. Years ago when I was on loan to MCC, we did some
> checking. On LMI's, the break even point (speedwise) between alists and hash
> tables was at 7 elements. On the Symbolics, it was something like 12. That
> meant that if you had fewer than 7 elements in your "table", an alist was
> faster. If more than 12, then the hashtable was faster. In between, it
> depends. It'd be interesting to know what the break even point is for the
> various CL implementations.
Right; bad assumption on my part. I tend to think of larger lists and
tables, but it could be that what is wanted is smaller than the
threshold.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
In article <············@spitting-spider.aracnet.com>, ·······@mikemac.com
wrote:
> Ah, not necessarily so. Years ago when I was on loan to MCC, we did some
> checking. On LMI's, the break even point (speedwise) between alists and hash
> tables was at 7 elements. On the Symbolics, it was something like 12. That
> meant that if you had fewer than 7 elements in your "table", an alist was
> faster. If more than 12, then the hashtable was faster. In between, it
> depends.
Symbolics Genera has the idea of "Tables". See Book 7
"Symbolics Common Lisp, Language Concepts", Chapter 5 "Table Management".
Tables are being created by calling MAKE-HASH-TABLE.
"One of the features of this facility is that tables change
internal representations based on the initial keywords
to MAKE-HASH-TABLE, the current size of the table,
and the type of the data set. This means that the table
changes at run-time as the table grows and shrinks.".
--
http://www.lavielle.com/~joswig
·······@mikemac.com (Mike McDonald) writes:
> In article <·············@beta.franz.com>,
> Duane Rettig <·····@franz.com> writes:
>
> > If so, then ignore the rest of this post; there's little you can do
> > about hard requirements. But if you are able to work with hash-tables,
> > they tend to be much more efficient than alists,
>
> Ah, not necessarily so. Years ago when I was on loan to MCC, we did some
> checking. On LMI's, the break even point (speedwise) between alists and hash
> tables was at 7 elements. On the Symbolics, it was something like 12. That
> meant that if you had fewer than 7 elements in your "table", an alist was
> faster. If more than 12, then the hashtable was faster. In between, it
> depends. It'd be interesting to know what the break even point is for the
> various CL implementations.
>
Of course. Note that - depending on the specific implementation/platform -
the performance of SORT could be improved by using a "slower"
algortihm than 'quicksort' on the shorter subsequences
(e.g. 'insertion sort')
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 10 03 17, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
Duane Rettig <·····@franz.com> writes:
> I was just wondering; why the need to convert between hash tables and
> alists? Is there some interface that you are using that requires alists?
Well, mostly I'm learning Common Lisp.
The problem I'm looking at is working with discrete distributions,
i.e. stocastic variables.
For efficiency reasons, I want to use hash tables to represent these
distributions.
However, at the current stage of this project, I use plain (read) and
(print) for input and output, and hash tables are neither readable or
printable, so I convert to/from alists at that point.
So, I would do something like:
(setf one-die (alist-to-hash
'((1 . 1/6) (2 . 1/6) (3 . 1/6) (4 . 1/6) (5 . 1/6) (6 . 1/6))))
(setf two-dice (add-dist one-die one-die))
(print (hash-to-alist two-dice))
... and then getting something human-semireadable out of it.
Hope this clears up the intended purpi of the functions.
Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
Jack of a Few Trades.
"Just when you accept that life's a bitch, it has puppies."
Stig Hemmer <····@pvv.ntnu.no> writes:
> Duane Rettig <·····@franz.com> writes:
> > I was just wondering; why the need to convert between hash tables and
> > alists? Is there some interface that you are using that requires alists?
>
> Well, mostly I'm learning Common Lisp.
>
> The problem I'm looking at is working with discrete distributions,
> i.e. stocastic variables.
>
> For efficiency reasons, I want to use hash tables to represent these
> distributions.
It depends on the number of elements you are working with as to whether
or not it will be more efficient.
> However, at the current stage of this project, I use plain (read) and
> (print) for input and output, and hash tables are neither readable or
> printable, so I convert to/from alists at that point.
>
> So, I would do something like:
>
> (setf one-die (alist-to-hash
> '((1 . 1/6) (2 . 1/6) (3 . 1/6) (4 . 1/6) (5 . 1/6) (6 . 1/6))))
If you are distributing over integer increments (such as the six faces
of the die) then maybe (for example) an array of size 6 indexed by
(1- face) would be the most efficient representation. Arrays are
also readable, though the indices would be implied rather than
explicit.
How large might the distributions get?
> (setf two-dice (add-dist one-die one-die))
>
> (print (hash-to-alist two-dice))
>
> ... and then getting something human-semireadable out of it.
>
> Hope this clears up the intended purpi of the functions.
Yes, it does, thanks.
> Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
> Jack of a Few Trades.
> "Just when you accept that life's a bitch, it has puppies."
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
Thank you very much for your comments, all of you!
Duane Rettig <·····@franz.com> writes:
> > For efficiency reasons, I want to use hash tables to represent these
> > distributions.
>
> It depends on the number of elements you are working with as to whether
> or not it will be more efficient.
My original thought was that efficiency would only matter for large
distributions. I wouldn't care about miniscule gains at the lower end
of the scale. I _would_ care about potentionally large losses at the
high end of the scale.
Later I reallized I might be doing things where this mattered after
all, e.g. in situations where I was iterating over several small
distributions in nested loops.
Offhand I can think of a case where I would be doing the innermost
code 6^5=7776 times. This is still not a frighteningly large number,
but add a dozen more dice and it will be. [In case anybody wondered,
the five-dice example is from the game Risk]
I'm not going to worry about this... yet.
> If you are distributing over integer increments (such as the six faces
> of the die) then maybe (for example) an array of size 6 indexed by
> (1- face) would be the most efficient representation. Arrays are
> also readable, though the indices would be implied rather than
> explicit.
Hmmm... that would be much better, yes. Not everything I do will be
small positive integers, but most of it definitely will be. I will
keep this in mind for future improvments, by creating integer-only
alternatives to some of the routines.
> How large might the distributions get?
In the straight-forward cases, I would guess that most of them would
be rather few elements, and the largest a few dozen elements, max.
However, with the hash table implementation it will be tempting to
handle codependent variables as a distribution of a list of values.
E.g., the distribution of a sorted list of two two-sided dice is:
(alist-to-hash '(((1 1) . 1/4)
((1 2) . 1/2)
((2 2) . 1/4)))
[In this case I would need a #'equal-type hash table]
The first advantage of doing this is that I now only have to handle,
in this case, three cases instead of four. With more and larger dice,
this advantage increases dramatically. If I'm throwing three 6-sixed
dice, the straight-forward way gives me 6^3=216 iterations, whereas
the sorted-list version has 56 distinct values. In the above five-dice
example this would be combined the other players two dice, where the
corresponing numbers are 36 and 21, for a (multiplied) total of either
7776 or 1176 iterations.
The second advantage is that I can do this sorting once and for all
for the two- and three-dice distributions, rather than doing them in
every iteration of the full five-dice nested loop. (252 vs 7776 times)
Again, the numbers aren't very large, but I foresee wishing to use
this code for larger problems. For example, a distribution of poker
hands would have 2598960 possible values...
Again, thank you all for your comments.
Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
Jack of a Few Trades.
"Just when you accept that life's a bitch, it has puppies."
Duane Rettig wrote in message <·············@beta.franz.com>...
>I was just wondering; why the need to convert between hash tables and
>alists? Is there some interface that you are using that requires alists?
>
>If so, then ignore the rest of this post; there's little you can do
>about hard requirements. But if you are able to work with hash-tables,
>they tend to be much more efficient than alists [...]
For one, an alist can be readably printed.
Strictly speaking, the typical search time in hash tables is O(1) while in
alists it is O(N). Which means there is a threshold such that for a number
of elements below it, an alist is faster, above the threshold--the hash
table is faster. The threshold depends on the implementation, and for
reasonable implementations, 5 +/- 2 is probably a reasonable rule of thumb.
Though the FAQ, I think, quotes it to be around 50 in some extreme cases.
Now, if we talk about space efficiency, an alist has two cons cells overhead
per element, or 4N words. Fewer in a CDR-coding implementation (are there
any left)? A hash table efficiency depends on the implementation and the
table parameters, but they are likely to be more wasteful. Right now I am
looking at a hash table with default parameters in LW. It is a structure
with 17 slots, holding a bucket vector, and each occupied bucket is an
alist. That is, the overhead space taken up by the buckets is the same as
what an alist would take up, plus the space taken up by the bucket vector,
plus the hash table structure. The table I am looking at holds 50 elements,
with the bucket vector length 138. The total structure, vector, and bucket
alists space is 355 words (plus, possibly, the headers of the structure and
the vector objects). An alist of 50 elements would take up 200 words.
--Vassili
"Vassili Bykov" <·······@objectpeople.com> writes:
> Duane Rettig wrote in message <·············@beta.franz.com>...
> >I was just wondering; why the need to convert between hash tables and
> >alists? Is there some interface that you are using that requires alists?
> >
> >If so, then ignore the rest of this post; there's little you can do
> >about hard requirements. But if you are able to work with hash-tables,
> >they tend to be much more efficient than alists [...]
>
> For one, an alist can be readably printed.
>
> Strictly speaking, the typical search time in hash tables is O(1) while in
> alists it is O(N). Which means there is a threshold such that for a number
> of elements below it, an alist is faster, above the threshold--the hash
> table is faster. The threshold depends on the implementation, and for
> reasonable implementations, 5 +/- 2 is probably a reasonable rule of thumb.
> Though the FAQ, I think, quotes it to be around 50 in some extreme cases.
Got it; this was a braino on my part.
> Now, if we talk about space efficiency, an alist has two cons cells overhead
> per element, or 4N words.
Actually, I was speaking not of space efficiency, but of consing efficiency,
especially wrt converting back and forth between the two different
representations. Whichever representation is used by the original
poster, a lot of consing could be saved by sticking to one representation.
> Fewer in a CDR-coding implementation (are there any left)?
Not on general purpose machines, that I know of.
On the subject of space (as opposed to consing):
> A hash table efficiency depends on the implementation and the
> table parameters, but they are likely to be more wasteful. Right now I am
> looking at a hash table with default parameters in LW. It is a structure
> with 17 slots, holding a bucket vector, and each occupied bucket is an
> alist. That is, the overhead space taken up by the buckets is the same as
> what an alist would take up, plus the space taken up by the bucket vector,
> plus the hash table structure. The table I am looking at holds 50 elements,
> with the bucket vector length 138. The total structure, vector, and bucket
> alists space is 355 words (plus, possibly, the headers of the structure and
> the vector objects). An alist of 50 elements would take up 200 words.
This is why we converted to flat hash tables in Allegro CL 4.2 and later;
a hash-table of size 50 consists of exactly three objects: a hash-table
structure of 8 words, a key vector of 83 (actually 84) words, and an
optional value vector, also of size 84; total size: 176 words. There is no
alist per bucket; each key/value is stored directly. [BTW, the optional value
vector gives you an extension that allows you to store keys only; this is
a good way to share conses or any other read-only resource.]
The base space overhead in an Allegro CL hash-table (i.e. the space used by
(make-hash-table :size 0) is 8 words for the table structure plus 3 (actually
4) words per vector, for a total of 16 words. This is obviously much more
expensive than the 0 (!) words needed by an alist, but at 4 words per element
in an alist and average 3 words per element in a hash-table (assuming a
rehash-threshold of .67) the space (not access time) efficiency crossover
threshold is at 16 elements.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 ·····@Franz.COM (internet)
Duane Rettig <·····@franz.com> wrote:
>I was just wondering; why the need to convert between hash tables and
>alists? Is there some interface that you are using that requires alists?
I've long had these functions in my standard lisp toolkit, I use them for
readably printing out hashtable contents to a file with the lisp read/print
mechanisms. So for me it always arises as a persistence need (in those cases
where some other persistence solution is not available). If you're doing this,
don't forget to handle circular references...
Where's CLTPAL when you need it... (Common Lisp, The Persistent Application
Language)
D. Tenny
············@mediaone.net - no spam please
Stig Hemmer <····@pvv.ntnu.no> writes:
> > (defun hash-table-to-alist (ht)
> > (let ((new-alist ()))
> > (loop for k being each hash-key in ht
> > do (setf new-alist (acons k (gethash k ht) new-alist)))
> > new-alist))
> >
> > ;;; The USING clause does not work well in CMUCL.
>
>
> For comparison, my own code:
>
> (defun hash-to-alist (hash)
> "Returns an alist with same key/value pairs as argument HASH."
> (loop for key being each hash-key in hash
> collect (cons key (gethash key hash))))
>
Yep. This one is better.
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 10 03 17, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
Marco Antoniotti wrote in message ...
>"Vassili Bykov" <·······@objectpeople.com> writes:
>> Cute would be hash->alist, like in Scheme.
>
>Nope! The '->' is not CL style. 'alist-to-hash-table' and
>'hash-table-to-alist' seem more sensible.
>
> [...]
>
>Cheers
>
>The Code Police
Umm... sorry Sir...won't happen again...don't mean no harm...just tried to
be cute... :-)
Seriously, I use foo-to-bar and foop myself, but apart from tradition I
don't see why they are more sensible than foo->bar and foo?. Just one of
those sacred egg breaking dilemmas...
--Vassili
Vassili Bykov wrote in message ...
>David Cooper wrote in message <·················@genworks.com>...
>>Stig Hemmer wrote:
>>>
>>> I was just writing a couple of functions for converting from hash to
>>> alist and vice versa.
>>>
>>> I'm wondering what to name these functions. Is it customary to use
>>> "hash-to-alist" or "alist-from-hash" or something else?
>>>
>>
>>You could get cute and name them hash2alist and alist2hash
>
>Cute would be hash->alist, like in Scheme.
One has to ask the question - why not just use a construction type function
like
(make-alist obj) and use typecase on the parameter to switch to code to "do
the right thing" for the given parameter type? Or am I missing something?
--
Frank A. Adrian
First DataBank
············@firstdatabank.com (W)
······@europa.com (H)
This message does not necessarily reflect those of my employer,
its parent company, or any of the co-subsidiaries of the parent
company.
"Frank Adrian" <············@firstdatabank.com> writes:
> One has to ask the question - why not just use a construction type
> function like (make-alist obj) and use typecase on the parameter to
> switch to code to "do the right thing" for the given parameter type?
> Or am I missing something?
Well, I could do that for make-alist, but I don't want to do that for
make-hash-table, since this is the name of an existing standard
function. The standard function doesn't have to functionality I need.
Stig Hemmer, perl -e 'print "Not a Perl hacker.\n"'
Jack of a Few Trades.
"Just when you accept that life's a bitch, it has puppies."
Stig Hemmer <····@pvv.ntnu.no> writes:
> I was just writing a couple of functions for converting from hash to
> alist and vice versa.
>
> I'm wondering what to name these functions. Is it customary to use
> "hash-to-alist" or "alist-from-hash" or something else?
Personally, I'd shadow and extend COERCE.
... though you might have to add an extra argument to really do it
right since if you have hash-to-plist and plist-to-hash you won't be
able to tell whether something's an alist or plist from it's
representational type. Something like...
(defun my-package:coerce (datum to-type &key (from-type (type-of datum)))
(my-package:coerce-internal datum from-type to-type))
(defmethod my-package:coerce (datum from-type to-type)
(declare (ignore from-type))
(cl:coerce datum to-type))
(defmethod my-package:coerce ((datum hash-table)
from-type (to-type (eql 'alist)))
(hash-to-alist datum))
(defmethod my-package:coerce ((datum list) (from-type 'alist)
(to-type 'hash-table))
(alist-to-hash datum))
..etc.
To understand what the from-type is doing in there, see my paper
"EQUAL Rights--and Wrongs--in Lisp" from Lisp Pointers at:
http://world.std.com/~pitman/PS/EQUAL.html