Arc Forumnew | comments | leaders | submitlogin
2 points by palsecam 5633 days ago | link | parent

In 'genWIN->Nums,

   (until (is (len winset) set-count)
      (let n (rand:1up top)
        (if (>= n bottom) (insortnew < n winset))))
is not optimal. Because, say if `bottom' is 30 and `top' is 40, in nearly the 3/4 of times, you'll call 'rand but not use the result, and you'll make a wasted loop turn.

A solution:

   (def genWIN->Nums2 (set-count bottom top)
     "Generates a list of `set-count' random numbers, each
     in the range between `bottom' and `top' (inclusives).
     The generation doesn't waste any CPU cycle :-)."
      (let winset nil 
         (until (is (len winset) set-count)
            (let n (rand (- (1up top) bottom))
	       (insortnew < (+ n bottom) winset)))
         (prall:pretty-nums winset)))
The idea is, for `bottom'=30 and `top'=40, to get a random number between 0 and 11, and then add `bottom' to it.

The result:

   (time (repeat 1000
      (genWIN->Nums 1 30 40)))
   => 1908 msec.
   (time (repeat 1000
      (genWIN->Nums2 1 30 40)))
   => 706 msec.


3 points by thaddeus 5632 days ago | link

FYI - I decided to redefine the rand function.

   (def random (n1 (o n2 0))
        (if (is n2 0)
            (swap n1 n2))
          (+ (rand (- (1up n2) n1)) n1))
this will make my code more readable + less 1ups for future code.

   (until (is (len winset) set-count)
          (insortnew < (random bottom top) winset))
T.

-----

3 points by thaddeus 5631 days ago | link

eh-hem. oops. right when I said I need to think like you more palsecam - I didn't!

   (def random (n1 (o n2 0))
        (if (is n2 0)
            (swap n1 n2))
          (+ (rand (- (1up n2) n1)) n1))
I had been trying to allow (random n) to return 0 as a valid value, but given the poor performance - if I want that I can always use rand...

   arc> (time (repeat 1000 (random 50))) 
   time: 12 msec.

   arc> (time (repeat 1000 (rand 50)))
   time: 2 msec.

   .... so .... re-take :)

   (def random (n1 (o n2 nil))
        (if (no n2)
            (1up:rand n1)
            (+ (rand (- (1up n2) n1)) n1)))

   arc> (time (repeat 1000 (random 50)))
   time: 3 msec.
Just goes to show: don't get too fancy. :) T.

-----

2 points by palsecam 5630 days ago | link

Thanks for sharing your investigation & ideas on the question :-)

-----

2 points by thaddeus 5633 days ago | link

That's awesome. I hadn't gone that far... and have yet to create any sort of habitual thinking around optimizations... Need to think like you more. Thanks. T.

-----