[racket] static variables question

From: Rodolfo Carvalho (rhcarvalho at gmail.com)
Date: Sun Feb 19 20:33:46 EST 2012

Hello Joe,

I'd like to make a few suggestions also.

~ 1 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I repeat what Neil V. said:

Formatting-wise, you might consider generally putting newlines between each
> of the three parts of an "if" form.  It's easier to distinguish the parts
> at a glance, especially if the parts contain parens, and you can also
> sometimes better see symmetries/asymmetries between the branches.


And a similar rule would apply to let-, cond-, etc-clauses (i.e. the ones
around square brackets []).

So instead of

(let ([a 1] [b 2] [c 3])
   ...)

I'd write for clarity:

(let ([a 1]
      [b 2]
      [c 3])
  ...)



~ 2 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The three `cond' uses are like `if's. They only have 1 test and an else
clause. So considering the cond's and if's, the code branches like this:

cond --- if ---- [1]
  \          \---- [2]
   \
    \----- cond --- [3]
            \
             \------- cond ------ [4]
                        \----------- [5]


It is possible to replace a pattern like this:

(cond
   [..a..]
   [else (cond
               [..b..]
               ...)])

With this simpler:

(cond
   [..a..]
   [..b..]
    ...)

That's one of the things that makes cond's different than if's...

After applying the above, the branching structure becomes:

cond --- if ---- [1]
  |          \---- [2]
  |------ [3]
  |------ [4]
  |------ [5]



~ 3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Using DrRacket's Debugger, I noticed that to compute (factor 4) the code
was iterating many unnecessary times in the loop, until the
candidate-primes list was exhausted.

Looking back at the code, we see that there's only one way to stop the
recursion, which is when (and (empty? candidate-primes) (>= end isqrtx))
holds true.
So even when we want to factorize small numbers we have to go through the
entire list of computed primes.
This suggests rethinking about the conditions...


Here's the code with my changes:


; function to create a list of prime factors of a number
; invoke as (factor n)
(define (factor n)
  (let loop-factors ([facts '()]
                     [x n]
                     [start 2]
                     [end 1000]
                     [candidate-primes (primes-from-to 2 1000)])
    (define isqrtx (integer-sqrt x))
    (cond
      [(and (empty? candidate-primes)
            (>= end isqrtx))
       (if (= 1 x)
           facts
           (append facts (list x)))]
      [(empty? candidate-primes)
       ; attempt to pull in more primes in an efficient manner
       (set! start end)
       (set! end (* 2 end))
       (when (> (* 1.5 end) isqrtx)
         (set! end isqrtx))
       (loop-factors facts
                     x
                     start
                     end
                     (primes-from-to start end))]
      [(zero? (remainder x (first candidate-primes)))
       (loop-factors (append facts (list (first candidate-primes)))
                     (quotient x (first candidate-primes))
                     start
                     end
                     candidate-primes)]
      [else
       (loop-factors facts
                     x
                     start
                     end
                     (rest candidate-primes))])))



[]'s

Rodolfo Carvalho
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20120219/d62410c3/attachment.html>

Posted on the users mailing list.