gistfile1.clj

; Uses nothing mutable. Works, but I want to see if exploiting mutability makes it faster.
(def primes3
  (lazy-cat [2 3 5 7]
            (let [update-map (fn update-map [step-map start step]
                               (assoc step-map
                                      (loop [i (+ start step)] (if (nil? (step-map i)) i (recur (+ step i))))
                                      step))
                  sieve (fn sieve [c step-map p primes]
                          (if (contains? step-map c)
                            (recur (+ 2 c) (update-map (dissoc step-map c) c (get step-map c)) p primes)
                            (if (< c (* p p))
                              (lazy-seq (cons c (sieve (+ 2 c) step-map p primes)))
                              (recur (+ 2 c) (update-map step-map c (* 2 p)) (first primes) (rest primes)))))]
              (sieve 9 {} 3 (drop 2 primes3)))))

; Uses a transient to save time. Works, but I'm forced to use persistent!, which seems to be slow for large maps.
(def primes4
  (lazy-cat [2 3 5 7]
            (letfn [(sieve [c step-map p primes]
                      (loop [c c step-map (transient step-map) p p primes primes]
                        (if (not (nil? (step-map c)))
                          (recur (+ 2 c)
                                 (let [step (step-map c)
                                       n (loop [i (+ c step)] (if (nil? (step-map i)) i (recur (+ step i))))]
                                   (assoc! (dissoc! step-map c) n step))
                                 p
                                 primes)
                          (if (< c (* p p))
                            (lazy-seq (cons c (sieve (+ 2 c) (persistent! step-map) p primes))) ; I can't use recur here, so I'm forced to call persistent!
                            (recur (+ 2 c)
                                   (let [step (* 2 p)
                                         n (loop [i (+ c step)] (if (nil? (step-map i)) i (recur (+ step i))))]
                                     (assoc! step-map n step))
                                   (first primes)
                                   (rest primes))))))]
              (sieve 9 {} 3 (drop 2 primes4)))))

; Moves the transient outside of sieve, to enable me to recurse in the lazy-seq without calling persistent!
; Doesn't work for some reason; it produces incorrect results after the first fifty or so primes.
(def primes1
  (lazy-cat [2 3 5 7]
            (let [step-map (transient {})
                  update-map (fn update-map [start step]
                               (assoc! step-map
                                       (loop [i (+ start step)] (if (nil? (step-map i)) i (recur (+ step i))))
                                       step))
                  sieve (fn sieve [c p primes]
                          (if (not (nil? (step-map c)))
                            (do
                              (update-map c (step-map c))
                              (dissoc! step-map c)
                              (recur (+ 2 c) p primes))
                            (if (< c (* p p))
                              (lazy-seq (cons c (sieve (+ 2 c) p primes)))
                              (do
                                (update-map c (* 2 p))
                                (recur (+ 2 c) (first primes) (rest primes))))))]
              (sieve 9 3 (drop 2 primes1)))))

; Uses a variable map and set!. Meant for comparison with primes1.
(def ^:dynamic step-map {})
(def primes2
  (lazy-cat [2 3 5 7]
            (let [update-map (fn update-map [start step]
                              (set! step-map
                                    (assoc step-map
                                      (loop [i (+ start step)] (if (nil? (step-map i)) i (recur (+ step i))))
                                      step)))
                  sieve (fn sieve [c p primes]
                          (if (not (nil? (step-map c)))
                            (do
                              (update-map c (step-map c))
                              (set! step-map (dissoc step-map c))
                              (recur (+ 2 c) p primes))
                            (if (< c (* p p))
                              (lazy-seq (cons c (sieve (+ 2 c) p primes)))
                              (do
                                (update-map c (* 2 p))
                                (recur (+ 2 c) (first primes) (rest primes))))))]
              (sieve 9 3 (drop 2 primes2)))))

; Is passed a transient instead of creating one. Works.
(def primes5
  (lazy-cat [2 3 5 7]
            (let [update-map (fn update-map [step-map start step]
                               (assoc! step-map
                                       (loop [i (+ start step)] (if (nil? (step-map i)) i (recur (+ step i))))
                                       step))
                  sieve (fn sieve [c step-map p primes]
                          (if (nil? (step-map c))
                            (if (< c (* p p))
                              (lazy-seq (cons c (sieve (+ 2 c) step-map p primes)))
                              (recur (+ 2 c) (update-map step-map c (* 2 p)) (first primes) (rest primes)))
                            (let [step (get step-map c)]
                              (recur (+ 2 c) (update-map (dissoc! step-map c) c step) p primes))))]
              (sieve 9 (transient {}) 3 (drop 2 primez)))))