Discussion of Common Lisp

qbg
 Posts: 64
 Joined: Mon Jun 30, 2008 1:05 pm
 Location: Minnesota
Post
by qbg » Sun Dec 07, 2008 9:14 pm
Paul Donnelly wrote:
I suspected someone would be along with a way to do it in one traversal, and I think I meant only that particular implementation when I referred to the necessity of iterating twice. Don't know why I would make a blanket statement like that.
To clarify: I was not implying that that you stated all implementations must iterate two (well, actually somewhere between one and two) times.
Furthermore, your solution is probably better, not only because it is shorter, but because I'd guess that it would be faster (unless calling random and testing for zero is sufficiently fast enough compared to taking a cdr of a cons cell on your implementation). The technique I demonstrated just shows how one can perform this task when you don't know how many elements you are going to get.

Paul Donnelly
 Posts: 148
 Joined: Wed Jul 30, 2008 11:26 pm
Post
by Paul Donnelly » Mon Dec 08, 2008 12:20 am
qbg wrote:Paul Donnelly wrote:
I suspected someone would be along with a way to do it in one traversal, and I think I meant only that particular implementation when I referred to the necessity of iterating twice. Don't know why I would make a blanket statement like that.
To clarify: I was not implying that that you stated all implementations must iterate two (well, actually somewhere between one and two) times.
Furthermore, your solution is probably better, not only because it is shorter, but because I'd guess that it would be faster (unless calling random and testing for zero is sufficiently fast enough compared to taking a cdr of a cons cell on your implementation). The technique I demonstrated just shows how one can perform this task when you don't know how many elements you are going to get.
And thank you for posting it, I found it interesting.

dmitry_vk
 Posts: 96
 Joined: Sat Jun 28, 2008 8:01 am
 Location: Russia, Kazan

Contact:
Post
by dmitry_vk » Mon Dec 08, 2008 6:41 am
qbg wrote:Paul Donnelly wrote:
Keep in mind, that one will have to iterate over the list twice, once to get its length, and once to get the random element (apologies if you know this already). It's probably fine for your purposes, but if it seems slower than it should be, consider either not using a list or storing the list length somewhere for quick lookup.
You should be able to do it in one traversal, at the cost of more calls to random:
Code: Select all
(defun randomnth (list)
(let ((element (car list))
(n 2))
(dolist (e (cdr list))
(if (zerop (random n))
(setf element e))
(incf n))
element))
In this solution, choice is random but the probability distribution is not uniform.

qbg
 Posts: 64
 Joined: Mon Jun 30, 2008 1:05 pm
 Location: Minnesota
Post
by qbg » Mon Dec 08, 2008 7:41 am
dmitry_vk wrote:qbg wrote:Paul Donnelly wrote:
Keep in mind, that one will have to iterate over the list twice, once to get its length, and once to get the random element (apologies if you know this already). It's probably fine for your purposes, but if it seems slower than it should be, consider either not using a list or storing the list length somewhere for quick lookup.
You should be able to do it in one traversal, at the cost of more calls to random:
Code: Select all
(defun randomnth (list)
(let ((element (car list))
(n 2))
(dolist (e (cdr list))
(if (zerop (random n))
(setf element e))
(incf n))
element))
In this solution, choice is random but the probability distribution is not uniform.
It should be. Think about the case of 4 items in a list. A table of probabilities would then be something like:
Code: Select all
1/1
1/2 1/2
2/3 2/3 1/3
3/4 3/4 3/4 1/4
First column is for choosing the first one, second for the second, etc. To get the total probability, you multiply all the elements in a column together, and you end up with 1/4 for each column. Note that the reason for it being triangular is that it doesn't matter what was chosen before you reach the number you want to produce.

jockc
Post
by jockc » Fri Dec 19, 2008 11:38 am
dmitry_vk wrote:qbg wrote:
In this solution, choice is random but the probability distribution is not uniform.
It should be. Think about the case of 4 items in a list. A table of probabilities would then be something like:
Code: Select all
1/1
1/2 1/2
2/3 2/3 1/3
3/4 3/4 3/4 1/4
First column is for choosing the first one, second for the second, etc. To get the total probability, you multiply all the elements in a column together, and you end up with 1/4 for each column. Note that the reason for it being triangular is that it doesn't matter what was chosen before you reach the number you want to produce.
Easy to demonstrate:
Code: Select all
(loop with hash = (makehashtable)
for count below 100000
for value = (randomnth '( 1 2 3 4 5 6 7 8 9 10))
do (incf (gethash value hash 0))
finally (maphash #'(lambda (k v) (format t "~a > ~a~%" k v)) hash))