Hi!
Is there a simple way to get a random hash-table element? The list
equivalent would be:
(elt *my-list* (random (length *my-list*)))
I cannot find anything on Google... Thanks for the answers!
Tonci
--
"For millions of years mankind lived just like the animals
Then something happened which unleashed the power of our imagination
We learned to talk"
Tonci Damjanic wrote:
> Hi!
> Is there a simple way to get a random hash-table element? The list
> equivalent would be:
>
> (elt *my-list* (random (length *my-list*)))
>
> I cannot find anything on Google... Thanks for the answers!
How about a combination of hash-table-count, random, and iteration over
the hash table?
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> Tonci Damjanic wrote:
> > Hi!
> > Is there a simple way to get a random hash-table element? The list
> > equivalent would be:
>
> > (elt *my-list* (random (length *my-list*)))
>
> > I cannot find anything on Google... Thanks for the answers!
>
> How about a combination of hash-table-count, random, and iteration over
> the hash table?
>
Easy enough. Of course, this is O(N). Having access to the
implementation you could possibly do this in O(1).
(defun random-hash-element (ht)
(loop with r = (random (hash-table-count ht))
for i from 0
for v being the hash-value of ht
when (= i r) return v))
Cheers
--
Marco
From: Kent M Pitman
Subject: Re: Getting a random hash-table element?
Date:
Message-ID: <uzlwy4b6a.fsf@nhplace.com>
Marco Antoniotti <·······@gmail.com> writes:
> On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> > Tonci Damjanic wrote:
> > > Is there a simple way to get a random hash-table element?
> > > The list equivalent would be:
> > > (elt *my-list* (random (length *my-list*)))
> > > I cannot find anything on Google... Thanks for the answers!
[puzzled and dismayed look] But, but... Google is and knows all...
> > How about a combination of hash-table-count, random, and iteration
> > over the hash table?
>
> Easy enough. Of course, this is O(N). Having access to the
> implementation you could possibly do this in O(1).
>
> (defun random-hash-element (ht)
> (loop with r = (random (hash-table-count ht))
> for i from 0
> for v being the hash-value of ht
> when (= i r) return v))
Well, I wasn't going to venture into the fray, but I can't resist a
good claim of impossibility. (Ok, maybe you didn't go quite so far as
to assert _that_, but I _was_ surprised that both you and Ken didn't
have a better suggestion to offer.)
Even WITHOUT access to the implementation's implementation or
knowledge of its algorithm, you can do a bit better if you play with
the problem constraints in some minor ways, for example, if you permit
an O(n) cost in storage space rather than in access time, AND if
you're able to control stores into the table, preferrably through some
better abstraction than I bothered with in this simple example (which
is intended only to show the general technique)...
(defvar *hash-key-tables* (make-hash-table))
(defvar *hash-key-table-initial-size* 100)
(defun puthash (key table value)
;; NOTE: without extra work, this won't be threadsafe
(multiple-value-bind (old-value present-p)
(gethash key table)
(declare (ignore old-value))
(unless present-p
;; This might take an occasional time hit to grow
;; the table, but only at storage time, not at access time.
(vector-push-extend key
(or (gethash table *hash-key-tables*)
(setf (gethash table *hash-key-tables*)
(make-array *hash-key-table-initial-size*
:adjustable t
:fill-pointer 0))))))
(setf (gethash key table) value))
(defun gethash-randomly (table)
;; Two gethash calls instead of 1 doesn't change the
;; algorithmic complexity of the access side. We will
;; assume that LENGTH of an array is O(1) and RANDOM
;; is likewise O(1). [AREF puzzled me for years since
;; it should be O(log(n)) but manages O(1) due to the
;; magic of machine hardware parallelism and
;; most-positive-fixnum.]
(let* ((key-table (gethash table *hash-key-tables*)))
(n-keys (length key-table))
(i (random n-keys))
(key (aref key-table i)))
(gethash key table)))
As always, caveat emptor; this was tested only very lightly ... and
even then I made some last minute cosmetic edits without retesting.
On Nov 28, 4:55 pm, Kent M Pitman <······@nhplace.com> wrote:
> Marco Antoniotti <·······@gmail.com> writes:
> > On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> > > Tonci Damjanic wrote:
> > > > Is there a simple way to get a random hash-table element?
> > > > The list equivalent would be:
> > > > (elt *my-list* (random (length *my-list*)))
> > > > I cannot find anything on Google... Thanks for the answers!
>
> [puzzled and dismayed look] But, but... Google is and knows all...
>
> > > How about a combination of hash-table-count, random, and iteration
> > > over the hash table?
>
> > Easy enough. Of course, this is O(N). Having access to the
> > implementation you could possibly do this in O(1).
>
> > (defun random-hash-element (ht)
> > (loop with r = (random (hash-table-count ht))
> > for i from 0
> > for v being the hash-value of ht
> > when (= i r) return v))
>
> Well, I wasn't going to venture into the fray, but I can't resist a
> good claim of impossibility. (Ok, maybe you didn't go quite so far as
> to assert _that_, but I _was_ surprised that both you and Ken didn't
> have a better suggestion to offer.)
>
> Even WITHOUT access to the implementation's implementation or
> knowledge of its algorithm, you can do a bit better if you play with
> the problem constraints in some minor ways, for example, if you permit
> an O(n) cost in storage space rather than in access time, AND if
> you're able to control stores into the table, preferrably through some
> better abstraction than I bothered with in this simple example (which
> is intended only to show the general technique)..
Well, of course. I stand corrected. Having the extra table does
solve the linear time problem with just some more space (which, this
day and age is not that big a deal unless you are dealing with very
large data-sets).
Apart from that, this is an interesting pattern that pops up while
programming several data structures. The simplest example that comes
to my mind is the implementation of a heap to be used in - e.g. - a
Dijkstra implementation. With a "general" enough implementation, it
is difficult to support the necessary REDUCE-KEY heap operation. But
I am veering off a tangent here :)
Cheers
--
Marco
Kent M Pitman wrote:
> Marco Antoniotti <·······@gmail.com> writes:
>
>
>>On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
>>
>>>Tonci Damjanic wrote:
>>>
>>>>Is there a simple way to get a random hash-table element?
>>>>The list equivalent would be:
>>>> (elt *my-list* (random (length *my-list*)))
>>>>I cannot find anything on Google... Thanks for the answers!
>
>
> [puzzled and dismayed look] But, but... Google is and knows all...
>
>
>>>How about a combination of hash-table-count, random, and iteration
>>>over the hash table?
>>
>>Easy enough. Of course, this is O(N). Having access to the
>>implementation you could possibly do this in O(1).
>>
>>(defun random-hash-element (ht)
>> (loop with r = (random (hash-table-count ht))
>> for i from 0
>> for v being the hash-value of ht
>> when (= i r) return v))
>
>
> Well, I wasn't going to venture into the fray, but I can't resist a
> good claim of impossibility. (Ok, maybe you didn't go quite so far as
> to assert _that_, but I _was_ surprised that both you and Ken didn't
...hmmm, doesn't "...that neither you nor Ken offered..." read a little
easierily?
> have a better suggestion to offer.)
>
> Even WITHOUT access to the implementation's implementation or
> knowledge of its algorithm, you can do a bit better if you play with
> the problem constraints in some minor ways, for example, if you permit
> an O(n) cost in storage space rather than in access time, AND if
> you're able to control stores into the table, preferrably through some
> better abstraction than I bothered with in this simple example (which
> is intended only to show the general technique)...
...which probably violates the intent of the homework, which I guessed
to have been to see if the student knew about maphash and
hash-table-count. EC for using loop instead of maphash.
:)
If this was not homework, recall that this is c.l.l and we are not
allowed to deviate from the specifications implicit in noob requests,
nor ask them why they need it, nor attempt to ascertain use patterns
which would signify which of space and time efficiency mattered most,
nor in any other way vary from the response a robot would give.
A bad robot, I mean.
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On 2007-11-28 12:58:54 -0500, Ken Tilton <···········@optonline.net> said:
> If this was not homework, recall that this is c.l.l and we are not
> allowed to deviate from the specifications implicit in noob requests,
> nor ask them why they need it, nor attempt to ascertain use patterns
> which would signify which of space and time efficiency mattered most,
> nor in any other way vary from the response a robot would give.
>
> A bad robot, I mean.
Pretty sure a "bad robot" would tell the homework-answer-seeking-noob
to just ask kenny...
... oh, you meant low-functioning-bad, not evil-bad ;^)
On Nov 28, 4:55 pm, Kent M Pitman <······@nhplace.com> wrote:
> Marco Antoniotti <·······@gmail.com> writes:
> > On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> > > Tonci Damjanic wrote:
> > > > Is there a simple way to get a random hash-table element?
> > > > The list equivalent would be:
> > > > (elt *my-list* (random (length *my-list*)))
> > > > I cannot find anything on Google... Thanks for the answers!
>
> [puzzled and dismayed look] But, but... Google is and knows all...
>
> > > How about a combination of hash-table-count, random, and iteration
> > > over the hash table?
>
> > Easy enough. Of course, this is O(N). Having access to the
> > implementation you could possibly do this in O(1).
>
> > (defun random-hash-element (ht)
> > (loop with r = (random (hash-table-count ht))
> > for i from 0
> > for v being the hash-value of ht
> > when (= i r) return v))
>
> Well, I wasn't going to venture into the fray, but I can't resist a
> good claim of impossibility. (Ok, maybe you didn't go quite so far as
> to assert _that_, but I _was_ surprised that both you and Ken didn't
> have a better suggestion to offer.)
>
> Even WITHOUT access to the implementation's implementation or
> knowledge of its algorithm, you can do a bit better if you play with
> the problem constraints in some minor ways, for example, if you permit
> an O(n) cost in storage space rather than in access time, AND if
> you're able to control stores into the table, preferrably through some
> better abstraction than I bothered with in this simple example (which
> is intended only to show the general technique)...
>
> (defvar *hash-key-tables* (make-hash-table))
> (defvar *hash-key-table-initial-size* 100)
>
> (defun puthash (key table value)
> ;; NOTE: without extra work, this won't be threadsafe
> (multiple-value-bind (old-value present-p)
> (gethash key table)
> (declare (ignore old-value))
> (unless present-p
> ;; This might take an occasional time hit to grow
> ;; the table, but only at storage time, not at access time.
> (vector-push-extend key
> (or (gethash table *hash-key-tables*)
> (setf (gethash table *hash-key-tables*)
> (make-array *hash-key-table-initial-size*
> :adjustable t
> :fill-pointer 0))))))
> (setf (gethash key table) value))
>
> (defun gethash-randomly (table)
> ;; Two gethash calls instead of 1 doesn't change the
> ;; algorithmic complexity of the access side. We will
> ;; assume that LENGTH of an array is O(1) and RANDOM
> ;; is likewise O(1). [AREF puzzled me for years since
> ;; it should be O(log(n)) but manages O(1) due to the
> ;; magic of machine hardware parallelism and
> ;; most-positive-fixnum.]
> (let* ((key-table (gethash table *hash-key-tables*)))
> (n-keys (length key-table))
> (i (random n-keys))
> (key (aref key-table i)))
> (gethash key table)))
>
> As always, caveat emptor; this was tested only very lightly ... and
> even then I made some last minute cosmetic edits without retesting.
What if populating the hash table is out of our control?
Isn't there some associative array container like skip list or self-
balancing binary search tree that implemented as a library could give
us easy access to random element without exposing it's
implementation. Or some container Alist could do the trick easily but
it's inefficient.
Slobodan
On Nov 28, 4:06 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Nov 28, 4:55 pm, Kent M Pitman <······@nhplace.com> wrote:
>
>
>
> > Marco Antoniotti <·······@gmail.com> writes:
> > > On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> > > > Tonci Damjanic wrote:
> > > > > Is there a simple way to get a random hash-table element?
> > > > > The list equivalent would be:
> > > > > (elt *my-list* (random (length *my-list*)))
> > > > > I cannot find anything on Google... Thanks for the answers!
>
> > [puzzled and dismayed look] But, but... Google is and knows all...
>
> > > > How about a combination of hash-table-count, random, and iteration
> > > > over the hash table?
>
> > > Easy enough. Of course, this is O(N). Having access to the
> > > implementation you could possibly do this in O(1).
>
> > > (defun random-hash-element (ht)
> > > (loop with r = (random (hash-table-count ht))
> > > for i from 0
> > > for v being the hash-value of ht
> > > when (= i r) return v))
>
> > Well, I wasn't going to venture into the fray, but I can't resist a
> > good claim of impossibility. (Ok, maybe you didn't go quite so far as
> > to assert _that_, but I _was_ surprised that both you and Ken didn't
> > have a better suggestion to offer.)
>
> > Even WITHOUT access to the implementation's implementation or
> > knowledge of its algorithm, you can do a bit better if you play with
> > the problem constraints in some minor ways, for example, if you permit
> > an O(n) cost in storage space rather than in access time, AND if
> > you're able to control stores into the table, preferrably through some
> > better abstraction than I bothered with in this simple example (which
> > is intended only to show the general technique)...
>
> > (defvar *hash-key-tables* (make-hash-table))
> > (defvar *hash-key-table-initial-size* 100)
>
> > (defun puthash (key table value)
> > ;; NOTE: without extra work, this won't be threadsafe
> > (multiple-value-bind (old-value present-p)
> > (gethash key table)
> > (declare (ignore old-value))
> > (unless present-p
> > ;; This might take an occasional time hit to grow
> > ;; the table, but only at storage time, not at access time.
> > (vector-push-extend key
> > (or (gethash table *hash-key-tables*)
> > (setf (gethash table *hash-key-tables*)
> > (make-array *hash-key-table-initial-size*
> > :adjustable t
> > :fill-pointer 0))))))
> > (setf (gethash key table) value))
>
> > (defun gethash-randomly (table)
> > ;; Two gethash calls instead of 1 doesn't change the
> > ;; algorithmic complexity of the access side. We will
> > ;; assume that LENGTH of an array is O(1) and RANDOM
> > ;; is likewise O(1). [AREF puzzled me for years since
> > ;; it should be O(log(n)) but manages O(1) due to the
> > ;; magic of machine hardware parallelism and
> > ;; most-positive-fixnum.]
> > (let* ((key-table (gethash table *hash-key-tables*)))
> > (n-keys (length key-table))
> > (i (random n-keys))
> > (key (aref key-table i)))
> > (gethash key table)))
>
> > As always, caveat emptor; this was tested only very lightly ... and
> > even then I made some last minute cosmetic edits without retesting.
>
> What if populating the hash table is out of our control?
If that is the case (unlikely), and you have no knowledge of how the
hashing algorithm works, you are well and truly screwed if you need
O(1) random access without preparation, etc... Use a different data
structure, or trade space for time.
> Isn't there some associative array container like skip list or self-
> balancing binary search tree that implemented as a library could give
> us easy access to random element without exposing it's
> implementation. Or some container Alist could do the trick easily but
> it's inefficient.
Unfortunately, there isn't a universally best data structure. There's
no good reason for this, as far as I can tell, but it does seem to be
a fact of life, and, incidentally, of computation. I've always thought
that computer science is the best tutor of morals available. If
resources were unlimited it would be hard to find a man not an angel,
but not hard to find a universal data structure. Draw your own
conclusions.
At any rate, think about why people accept that performance for
hashes. It is all about the trade-offs. There is, in addition to the
Golden Rule, a Rule of Iron: You can do whatever you want, if you are
willing to pay its price. Note that "X could solve this inefficiency
easily, but it is inefficient" is... well, it is not moral.
From: Kent M Pitman
Subject: Re: Getting a random hash-table element?
Date:
Message-ID: <uzlwx48vo.fsf@nhplace.com>
··········@aol.com writes:
> > What if populating the hash table is out of our control?
>
> If that is the case (unlikely), and you have no knowledge of how the
> hashing algorithm works, you are well and truly screwed if you need
> O(1) random access without preparation, etc... Use a different data
> structure, or trade space for time.
Well, again, if you take the question literally, this appears to be sound
advice. But your response seems to me like it includes and then glosses
over a design option that the OP might not be considering.
(It doesn't sound like you were precluding this analysis, I just get
worried that people don't stop to consider such things... so much of
the world today seems to be taken at face value, unexamined. I
somehow blame television advertising for instilling in people a desire
to buy things pre-packaged, ready to microwave.)
The preparation might be able to be on-demand, if it's known that the
population of the table won't be going on asynchronously (and/or you
can block it during the time of a series of accesses) and if there are
enough accesses about to happen to justify the stop-and-index.
That is, it's going to take O(n) time per call to the gethash-randomly
function for each time you call it. If that's a lot of times, k, then
the true time for your algorithm is O(n*k) and if k is typically a
function of n, then O(n^2). If, by contrast, the situation is such
that one can stop and do a single O(n) pass to fill a key table such
as I was suggesting and then use it n times, you get O(n)+O(k*1),
which even if k goes like n is still O(n)+O(n), which is O(n), not
O(n^2). Or so it seems to me at this late hour of the night--someone
can double-check my math and/or chide me for my sloppy notation later.
> > Isn't there some associative array container like skip list or self-
> > balancing binary search tree that implemented as a library could give
> > us easy access to random element without exposing it's
> > implementation. Or some container Alist could do the trick easily but
> > it's inefficient.
>
> Unfortunately, there isn't a universally best data structure. There's
> no good reason for this, as far as I can tell, but it does seem to be
> a fact of life, and, incidentally, of computation. I've always thought
> that computer science is the best tutor of morals available. If
> resources were unlimited it would be hard to find a man not an angel,
> but not hard to find a universal data structure. Draw your own
> conclusions.
An excellent and pithy observation. Thanks!
> At any rate, think about why people accept that performance for
> hashes. It is all about the trade-offs. There is, in addition to the
> Golden Rule, a Rule of Iron: You can do whatever you want, if you are
> willing to pay its price. Note that "X could solve this inefficiency
> easily, but it is inefficient" is... well, it is not moral.
But likewise people view the world statically, and tend to accept
problem descriptions on their face. As they are often not masters of
their programming tools, they are equally often (in your analogy
space) not masters of their morality space. If they are not
linguistically confident, they may confuse being flexible about
shifting around a problem involving morality with being flexible about
shifting morality around in a problem, the two being very different
things. So when confronted with an issue involving trade-offs, one
can get so caught up in the set of choices presented that one forgets
one can often, in the real world, change the parameters of test so as
to improve the programmatic (or moral) options available.
[Reference here James Kirk's solution to the Kobayashi Maru in Star
Trek II: The Wrath of Kahn (which I personally classify as the
all-time best movie of all time, and not just because I'm partial to
Trek things).]
Marco Antoniotti <·······@gmail.com> writes:
> On Nov 28, 3:54 am, Ken Tilton <···········@optonline.net> wrote:
> > Tonci Damjanic wrote:
> > > Hi!
> > > Is there a simple way to get a random hash-table element? The list
> > > equivalent would be:
> >
> > > (elt *my-list* (random (length *my-list*)))
> >
> > > I cannot find anything on Google... Thanks for the answers!
> >
> > How about a combination of hash-table-count, random, and iteration over
> > the hash table?
> >
>
> Easy enough. Of course, this is O(N).
So is elt, and the OP seems OK with that.
> Having access to the implementation you could possibly do this in
> O(1).
Or, you just do it yourself with the cost of another table :-|. That
may or may not be acceptable. The second table is hashed on counting
numbers which are mapped 1-1 with the "primary" table's entries, i.e.,
the secondary table's (k v) pairs have v the key (or maybe the actual
corresponding value - that could save some cycles later) for an entry
into "primary" table and k just its ordinal count of entry into the
"primary" table.
Then you have
(gethash (gethash (random (hash-table-count primary-tbl)) secondary-tbl)
primary-tbl)
Of course this means the requirement of the extra overhead of
(setf (gethash (chash-table-count primary-table) secondary-tbl) new-key)
whenever you insert (new-key the-primary-value) into the primary table...
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
On Wed, 28 Nov 2007 03:13:41 +0100, Tonci Damjanic wrote:
> <cut>
Thank you all for your advices, some of them evolved into something more
complicated than I had in my mind.
I've taken Ken's advice (the first one) and coded something like this:
(defun get-random-element ()
(let (position)
(setf position (random (hash-table-count *my-table*)))
(find-selected-symbol position)))
(defun find-selected-element (n)
(let (result)
(maphash #'(lambda (k v)
(declare (ignore v))
(if (= n 0)
(progn
(setf result k)
(decf n))
(decf n)))
*my-table*)
result))
It's a bit ugly, but it works fine... :)
Tonci
--
"For millions of years mankind lived just like the animals
Then something happened which unleashed the power of our imagination
We learned to talk"
Tonci Damjanic wrote:
> On Wed, 28 Nov 2007 03:13:41 +0100, Tonci Damjanic wrote:
>
>
>><cut>
>
>
> Thank you all for your advices, some of them evolved into something more
> complicated than I had in my mind.
>
> I've taken Ken's advice (the first one) and coded something like this:
>
> (defun get-random-element ()
> (let (position)
> (setf position (random (hash-table-count *my-table*)))
> (find-selected-symbol position)))
The nice thing about every form returning a value is:
(find-selected-symbol
(random (hash-table-count *my-table*)))
But we get more mileage out of code when it is parameterized. Sure, you
could rebind the special before each call and sometimes that is
appropriate (when other wise you are just forever having to pass the
table around) but by default I'd like to see a parameter:
(defun gre (h)
(fss (random (hash-table-count h))))
As for fss...
>
> (defun find-selected-element (n)
> (let (result)
> (maphash #'(lambda (k v)
> (declare (ignore v))
> (if (= n 0)
> (progn
> (setf result k)
> (decf n))
> (decf n)))
> *my-table*)
> result))
>
> It's a bit ugly, but it works fine... :)
Yep, and I like the counting down and testing for zero instead of
counting up with a second variable.
When you are ready (and don't wait too long) learn loop:
(defun gre-fss (h)
(loop for x downfrom (random (hash-table-count h))
for v being the hash-values of h
when (zerop x) return v))
kt
--
http://www.theoryyalgebra.com/
"In the morning, hear the Way;
in the evening, die content!"
-- Confucius
On Thu, 29 Nov 2007 00:41:47 -0500, Ken Tilton wrote:
> The nice thing about every form returning a value is:
>
> (find-selected-symbol
> (random (hash-table-count *my-table*)))
Initially, I've written this in one line. As that was too ugly, I've
introduced new variable in order to clarify things. But now it looks OK,
especially with this line break. :)
> But we get more mileage out of code when it is parameterized. Sure, you
> could rebind the special before each call and sometimes that is
> appropriate (when other wise you are just forever having to pass the
> table around) but by default I'd like to see a parameter:
>
> (defun gre (h)
> (fss (random (hash-table-count h))))
You're right, but in this situation *my-table* is the table used throughout
the whole program and passing it around as a parameter would be to
confusing. *my-table* is defined once, during initialization of parameters,
and used unmodified later.
> Yep, and I like the counting down and testing for zero instead of
> counting up with a second variable.
>
> When you are ready (and don't wait too long) learn loop:
>
> (defun gre-fss (h)
> (loop for x downfrom (random (hash-table-count h))
> for v being the hash-values of h
> when (zerop x) return v))
Alright, this is the simplicity I needed! Learning loop is my next lesson.
:)
Although my solution works, maphash shouldn't be used like I did...
Thanks!
Tonci
--
"For millions of years mankind lived just like the animals
Then something happened which unleashed the power of our imagination
We learned to talk"
Tonci Damjanic <··············@st.t-com.hr> writes:
> On Wed, 28 Nov 2007 03:13:41 +0100, Tonci Damjanic wrote:
>
> > <cut>
>
> I've taken Ken's advice (the first one) and coded something like this:
>
> (defun get-random-element ()
> (let (position)
> (setf position (random (hash-table-count *my-table*)))
> (find-selected-symbol position)))
Slightly more lisp stylish, and flexible.
(defun get-random-element (hashtable)
(let ((position (random (hash-table-count hashtable))))
(find-hashtable-element hashtable position)))
or
(defun get-random-element (hashtable)
(find-hastable-element hashtable
(random (hash-table-count hashtable))))
Generally avoiding SETQ/SETF by binding values or just nesting calls is
more common in Lisp programming. Also, it's a good idea to make your
functions more generic by not including global constants. You then call
the functions like:
(get-random-element *my-table*)
> (defun find-selected-element (n)
> (let (result)
> (maphash #'(lambda (k v)
> (declare (ignore v))
> (if (= n 0)
> (progn
> (setf result k)
> (decf n))
> (decf n)))
> *my-table*)
> result))
And for something that is about twice as fast, on average:
(defun find-hashtable-element (hashtable n)
(maphash #'(lambda (k v)
(declare (ignore v))
(when (= n 0)
(return-from find-hashtable-element k))
(decf n))
hashtable))
--
Thomas A. Russ, USC/Information Sciences Institute
This works fine, even for hash-tables that are build at run-time:
For the value:
(defun random-ex-hash-value (table)
(loop repeat (1+ (random (hash-table-count table)))
for x being the hash-key of table
finally (return (gethash x table))))
For the key:
(defun random-ex-hash-key (table)
(loop repeat (1+ (random (hash-table-count table)))
for x being the hash-key of table
finally (return x)))
chris
"(typep 'nil (statisfies 'identity))" wrote:
> This works fine, even for hash-tables that are build at run-time:
> For the value:
> (defun random-ex-hash-value (table)
> (loop repeat (1+ (random (hash-table-count table)))
> for x being the hash-key of table
> finally (return (gethash x table))))
>
> For the key:
> (defun random-ex-hash-key (table)
> (loop repeat (1+ (random (hash-table-count table)))
> for x being the hash-key of table
> finally (return x)))
BTW, shouldn't this be (loop ... for x being the hash-keys ...). I
thought it was either BEING EACH HASH-KEY or BEING THE HASH-KEYS.
Damien Kick <·····@earthlink.net> wrote:
+---------------
| > (defun random-ex-hash-key (table)
| > (loop repeat (1+ (random (hash-table-count table)))
| > for x being the hash-key of table
| > finally (return x)))
|
| BTW, shouldn't this be (loop ... for x being the hash-keys ...).
| I thought it was either BEING EACH HASH-KEY or BEING THE HASH-KEYS.
+---------------
Nope, LOOP's syntax isn't really that "grammatical". ;-}
It's more of a "pick one from each of columns A, B, & C"
sort of thing, with column A being "{each | the}", column B
being "{hash-key | hash-keys}", and column C being "{in | of}".
Here's the relevant bit from CLHS "Macro LOOP":
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)]}
So both of the forms "each hash-keys" and "the hash-key" are legal
in LOOP, regardless of what your high-school English teacher might
have to say about them. ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607