# Wishful Coding

Didn't you ever wish your computer understood you?

## Take n distinct random items from a vector

Another IRC hacking session.  (ns test
(: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]
(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)))

(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))

(-> (scatter-plot x (map (partial plot-len  take-rand1) x) :series-label "shuffle" :legend true)
(add-points   x (map (partial plot-len  take-rand2) x) :series-label "filtered")
(add-points   x (map (partial plot-len  take-rand3) x) :series-label "reduce")
(add-points   x (map (partial plot-len  take-rand4) x) :series-label "iterate")
(save "len.png")) ; http://yfrog.com/5r80779474p

(-> (scatter-plot x (map (partial plot-take take-rand1) x) :series-label "shuffle" :legend true)
(add-points   x (map (partial plot-take take-rand2) x) :series-label "filtered")
(add-points   x (map (partial plot-take take-rand3) x) :series-label "reduce")
(add-points   x (map (partial plot-take take-rand4) x) :series-label "iterate")
(save "take.png")) ; http://yfrog.com/mr42647628p 