Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp.

(defun sundaram-sieve (limit)
  (let ((numbers (range 3 (+ limit 1) 2))
        (half (/ limit 2))
        (start 4))
    (dolist (step (range 3 (+ limit 1) 2))
      (dolist (i (range start half step))
        (setf (nth (- i 1) numbers) 0))
      (setq start (+ start (* 2 (+ step 1))))
      (if (> start half)
          (return (cons 2 (remove-if #'zerop numbers)))))))

Here range is defined as:

(defun range (min max step)
   (loop for n from min below max by step
      collect n))

How can i make the code above more functional and idiomatic? The use of setq and setf bothers me, not to mention that it takes 10 seconds to calculate with limit equal 100000, when the equivalent code in Python runs almost instantly.

share|improve this question

1 Answer 1

up vote 4 down vote accepted
  (let ((numbers (range 3 (+ limit 1) 2))

Above defines a list of numbers. Later you set various numbers to zero. That's not good for a list structure. Use a vector, an one-dimensional array.

(dolist (step (range 3 (+ limit 1) 2))

Creating the list and then iterating over it makes no sense. Use a LOOP statement directly.

  (dolist (i (range start half step))

Creating the list and then iterating over it makes no sense. Use a LOOP statement directly.

Example:

(defun sundaram-sieve (limit)
  (let ((numbers (coerce (cons 2 (range 3 (+ limit 1) 2)) 'vector))
        (half (/ limit 2))
        (start 4))
    (loop for step from 3 upto limit by 2 do
          (loop for i from start below half by step do
                (setf (aref numbers i) 0))
          (incf start (* 2 (1+ step)))
          (when (> start half)
            (return (remove 0 numbers))))))

Runs fast.

CL-USER 36 > (time (sundaram-sieve 100000))
Timing the evaluation of (SUNDARAM-SIEVE 100000)

User time    =        0.007
System time  =        0.000
Elapsed time =        0.004
Allocation   = 1646136 bytes
0 Page faults
#(2 3 5 7 11 13 17 ... 99971 99989 99991)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.