take_rand.clj

(ns shuffle.core
  (:use (incanter core charts)))

; naive, O(n+m)
(defn take-rand1 [n coll] (take n (shuffle coll)))

; lazy, O(n!@#$%m^&)
(defn take-rand2 [n coll]
  (let [coll (vec coll)]
    (take n (distinct (repeatedly #(rand-nth coll))))))

; reduce, reorder, subvec, O(m)
(defn take-rand3 [nr coll]
  (let [len (count coll)
        ; why doesn't rand-int take a start?
        rand-int (fn [lo hi] (+ lo (rand-int (- hi lo))))]
    (subvec (->> (range nr)
                 (reduce #(conj %1 [%2 (rand-int %2 len)]) [])
                 (reduce
                   (fn swap [a [i b]]
                      (assoc a b (get a i) i (get a b)))
                   coll))
            0 nr)))

; amalloy, O(m)
(defn take-rand4 [num coll]
  (first
   (nth
    (iterate (fn [[ret candidates]]
               (let [idx (rand-int (count candidates))]
                 [(conj ret (candidates idx))
                  (subvec (assoc candidates idx (candidates 0))
                          1)]))
             [[]
              coll])
    num)))

(letfn [(lazy-shuffle [coll]
          ((fn shuffle [coll]
             (lazy-seq
              (let [c (count coll)]
                (when-not (zero? c)
                  (let [n (rand-int c)]
                    (cons (get coll n)
                          (shuffle (pop! (assoc! coll n (get coll (dec c)))))))))))
           (transient coll)))]
  (defn take-rand5 [num coll]
    (take num (lazy-shuffle coll))))

(defn t [f]
  (let [start (. System (nanoTime))]
    (f)
     (- (. System (nanoTime)) start)))

(defn plot-len [f n]
  (let [coll (vec (range n))]
    (t #(doall (f 1000 coll)))))

(defn plot-take [f n]
  (let [coll (vec (range 100000))]
    (t #(doall (f n coll)))))

(def x (range 1000 100000 1000))

(defn points [f g]
  (System/gc)
  (map (partial f g) x))

(defn do-it []
  (-> (scatter-plot x (points plot-len  take-rand1) :series-label "shuffle" :legend true)
      (add-points   x (points plot-len  take-rand2) :series-label "filtered")
      (add-points   x (points plot-len  take-rand3) :series-label "reduce")
      (add-points   x (points plot-len  take-rand4) :series-label "iterate")
      (add-points   x (points plot-len  take-rand5) :series-label "lazy")
      (save "len.png")) ; http://i.imgur.com/SJ0pH.png

  (-> (scatter-plot x (points plot-take take-rand1) :series-label "shuffle" :legend true)
      (add-points   x (points plot-take take-rand2) :series-label "filtered")
      (add-points   x (points plot-take take-rand3) :series-label "reduce")
      (add-points   x (points plot-take take-rand4) :series-label "iterate")
      (add-points   x (points plot-take take-rand5) :series-label "lazy")
      (save "take.png"))) ; http://i.imgur.com/ExyD7.png