(defn lazy-primes [] (letfn [(enqueue [sieve n step] (let [m (+ n step)] (if (sieve m) (recur sieve m step) (assoc sieve m step)))) (next-sieve [sieve candidate] (if-let [step (sieve candidate)] (-> sieve (dissoc candidate) (enqueue candidate step)) (enqueue sieve candidate (+ candidate candidate)))) (next-primes [sieve candidate] (if (sieve candidate) (recur (next-sieve sieve candidate) (+ candidate 2)) (cons candidate (lazy-seq (next-primes (next-sieve sieve candidate) (+ candidate 2))))))] (cons 2 (lazy-seq (next-primes {} 3)))))and this one that is very close to what I wanted:

(defn sieve [n] (let [n (int n)] "Returns a list of all primes from 2 to n" (let [root (int (Math/round (Math/floor (Math/sqrt n))))] (loop [i (int 3) a (int-array n) result (list 2)] (if (>= i n) (reverse result) (recur (+ i (int 2)) (if (< i root) (loop [arr a inc (+ i i) j (* i i)] (if (>= j n) arr (recur (do (aset arr j (int 1)) arr) inc (+ j inc)))) a) (if (zero? (aget a i)) (conj result i) result)))))))and of course the one from contrib:

(defvar primes (concat [2 3 5 7] (lazy-seq (let [primes-from (fn primes-from [n [f & r]] (if (some #(zero? (rem n %)) (take-while #(<= (* % %) n) primes)) (recur (+ n f) r) (lazy-seq (cons n (primes-from (+ n f) r))))) wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])] (primes-from 11 wheel)))) "Lazy sequence of all the prime numbers.")Instead I came up with my own bad one...

(defn primes [max-num]( loop [numbers (range 2 max-num) primes [] p 2] (if (= (count numbers) 1) (conj primes (first numbers)) (recur (filter #(not= (mod % p) 0) numbers) (conj primes p) (first (rest numbers))))))Why is this so bad? Well it is horribly inefficient. It creates a list of integers up to the max-num that is the only input to the function. It then loops, each time removing all multiples of each prime -- just like a sieve is supposed to. However, most sieves take a prime p and remove 2p, 3p, 4p, etc. (often optimized to 3p, 5p, 7p, since all the even numbers are removed at the beginning.) This does the same thing, but it uses a filter to do it. So it goes through each member of the list to check if it is divisible by p. So it does way too many calculations. Next, it is constantly generating a new list of numbers to pass back into the loop. Maybe Clojure does some cleverness to make this not as memory inefficient as it sounds, but I don't think so.

So what is it that I did not like about the other many examples out there or suggested by the community? Most of them used a lazy sequence. That's great and very efficient. However, it's not a concept that is easy to implement in other, less functional languages (Go Clojure!) On the other hand, the Rich Hickey example is much closer to what I wanted to do. However, it uses Java arrays. There is no duplication of the list and the non-primes are eliminated efficiently. Using Java arrays just seems non-idiomatic to say the least. The other examples did for JavaOne all used variable length lists instead of arrays.

Anyways, I am satisfied to at least have a seemingly equivalent, idiomatic Clojure implementation. I looked at optimizing it through using type hints. I actually had to use a lot of type hints (4) to get a 10% decrease in speed. Anyways, not that this is out here, others will improve it, as that shouldn't be too hard to do!

## No comments:

Post a Comment