sieves.clj

;; Here are 4 different versions of the sieve function with slight changes to test my theories
;; around seq, chunked-seq and transducer (reduce) api.
;; Try running these yourself with: (run-all)

(declare sieves)
(defn run-all []
  (doseq [[k sieve] sieves] 
    (prn "Running:" k) 
    (dotimes [_ 5] 
      (time (sieve 10000)))))
  
;; Your original version
(defn sieve-original
   [limit]
   (loop [step 2
          acc (take limit (iterate inc 2))]
     (let [step (first (drop-while #(< % step) acc))]
       (if (nil? step)
         acc
         (recur (inc step) (doall (remove #(rem? % step) acc)))))))
;; Times:
"Running:" :original
"Elapsed time: 486.726698 msecs"
"Elapsed time: 488.568267 msecs"
"Elapsed time: 478.306653 msecs"
"Elapsed time: 485.596243 msecs"
"Elapsed time: 485.020587 msecs"

;; Testing my theory about chunked sequences I put the output of (take ) in a vector.
;; Vectors return chunked sequences: (chunked-seq? (seq [1 2 3])) => true
(defn sieve-with-chunked-seq
   [limit]
   (loop [step 2
          acc (vec (take limit (iterate inc 2)))]
     (let [step (first (drop-while #(< % step) acc))]
       (if (nil? step)
         acc
         (recur (inc step) (doall (remove #(rem? % step)  acc)))))))
;; Times:
"Running:" :chunked-seq
"Elapsed time: 393.645826 msecs"
"Elapsed time: 395.146193 msecs"
"Elapsed time: 404.397592 msecs"
"Elapsed time: 406.55445 msecs"
"Elapsed time: 399.499285 msecs"

;; Using (into [] xf coll) instead of the sequence api (remove ..).
;; (into [] ...) uses reduce, which has optimizations depending on which
;; collection you reduce over.
(defn sieve-transducer
   [limit]
   (loop [step 2
          acc (take limit (iterate inc 2))]
     (let [step (first (drop-while #(< % step) acc))]
       (if (nil? step)
         acc
         (recur (inc step) (into [] (remove #(rem? % step)) acc))))))
"Running:" :transducer
"Elapsed time: 260.845557 msecs"
"Elapsed time: 343.591049 msecs"
"Elapsed time: 270.091647 msecs"
"Elapsed time: 269.804429 msecs"
"Elapsed time: 276.559579 msecs"

;; Adding the optimization (vec (take ..)) to the transducer one. Shouldn't do much
;; because acc will be set to the vector of (into []) after the first loop.
(defn sieve-transducer-with-chunked-seq
   [limit]
   (loop [step 2
          acc (vec (take limit (iterate inc 2)))]
     (let [step (first (drop-while #(< % step) acc))]
       (if (nil? step)
         acc
         (recur (inc step) (into [] (remove #(rem? % step)) acc))))))
"Running:" :transducer-with-vec
"Elapsed time: 274.615852 msecs"
"Elapsed time: 263.544016 msecs"
"Elapsed time: 265.444625 msecs"
"Elapsed time: 280.678696 msecs"
"Elapsed time: 273.880648 msecs"
;; ^^^^^^^^^^^^^^^^^^^^ about the same results as :transducer


(def sieves {:original sieve-original 
             :chunked-seq sieve-with-chunked-seq 
             :transducer sieve-transducer 
             :transducer-with-vec sieve-transducer-with-chunked-seq})