I have a need for a lisp function yesno which, when called,
returns nil or t with about equal probability in a random
sequence. (pseudorandom, anyway). Its cycle could be on the order
of 16k. It would be nice to be both fast and small.
My efforts can be seen in http://www.cs.berkeley.edu/~fateman/lisp/yn.lisp
Anyone care to make suggestions?
Here's a taste..
(let* ((h (loop for i from 1 to 1000 collect (> (random 2) 0)))
(yn (nconc h h)))
(defun yesno()
(pop yn)))
;;Richard Fateman
rjf wrote:
> I have a need for a lisp function yesno which, when called,
> returns nil or t with about equal probability in a random
> sequence. (pseudorandom, anyway). Its cycle could be on the order
> of 16k. It would be nice to be both fast and small.
SBCL on my machine:
(time (let ((x 0))
(dotimes (i (expt 10 5))
(incf x (random 1.0)))
x))
Evaluation took:
0.004 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
0.00% CPU
9,176,977 processor cycles
0 bytes consed
50066.207
Why not simply
(defun yesno () (= (random 2) 0))
?
- Daniel
D Herring wrote:
> rjf wrote:
>> I have a need for a lisp function yesno which, when called,
>> returns nil or t with about equal probability in a random
>> sequence. (pseudorandom, anyway). Its cycle could be on the order
>> of 16k. It would be nice to be both fast and small.
>
> SBCL on my machine:
>
> (time (let ((x 0))
> (dotimes (i (expt 10 5))
> (incf x (random 1.0)))
> x))
> Evaluation took:
> 0.004 seconds of real time
> 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
> 0.00% CPU
> 9,176,977 processor cycles
> 0 bytes consed
> 50066.207
>
> Why not simply
> (defun yesno () (= (random 2) 0))
> ?
I take that back -- my timings are similar to yours. The simple
function isn't particularly fast, even though the underlying random
number generation is. Also note that the function-call overhead is a
large part of the execution time...
e.g. (defun dummy ())
(time (yesno)) => 2209 cycles (with optimize declarations)
(time (dummy)) => 1284 cycles (with optimize declarations)
So you tried generating a bunch of these up front and then traversing
the array...
- Daniel
Thanks for looking.
On Aug 5, 10:38 pm, D Herring <········@at.tentpost.dot.com> wrote:
> D Herring wrote:
....
> > (incf x (random 1.0)))
....
this is buggy. (incf x (random 1.0)) returns a float between 1.0 and
2.0
>
> > Why not simply
> > (defun yesno () (= (random 2) 0))
...
yes, that works, and I provide some times. We can go about 5X faster.
>
> So you tried generating a bunch of these up front and then traversing
> the array...
That's the general idea; or traversing a looped list. I though that
cache memory would take a hit with the list.
Not that I could see it in measurements. And should the array be bits
or words? And if bits, how best to translate
between 0/1 and nil/t ? an IF or an array reference.
I put SBCL 1.0.13 and Allegro CL 8.0 times in comments in the file.