Choose numbers at random

Discussion of Common Lisp

Re: Choose numbers at random

Postby 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.
qbg
 
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

Re: Choose numbers at random

Postby 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.
Paul Donnelly
 
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

Re: Choose numbers at random

Postby 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 random-nth (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.
dmitry_vk
 
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan

Re: Choose numbers at random

Postby 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 random-nth (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.
qbg
 
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

Re: Choose numbers at random

Postby 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 = (make-hash-table)
      for count below 100000
      for value = (random-nth '( 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))
jockc
 

Previous

Return to Common Lisp

Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 3 guests