Hi Steve,
Although the reduce is very Lispy, in this case it might be clearer
with loop/recur:
(defn random-sample [sample-size items]
(loop [num 0,
current [],
items items]
(if-let [item (first items)]
(if (< num sample-size)
(recur (inc num) (conj current item) (rest items))
(let [index (rand-int num)]
(if (< index sample-size)
(recur (inc num) (assoc current index item) (rest
items))
(recur (inc num) current (rest items)))))
current)))
It could go in clojure.contrib.seq-utils. I'll add it there if you
like.
-Stuart Sierra
On Nov 21, 5:40 pm, "[EMAIL PROTECTED]" <[EMAIL PROTECTED]> wrote:
> I needed a random sampling function for work and wrote this in
> Clojure.
>
> (defn random-sample
> "Take a random sample of size `sample-size' from the `items'
> sequence.
>
> This uses Algorithm R -- random sampling with a reservoir. It
> requires O(`sample-size') space and does not need to know the size of
> `items' ahead of time. Described in Knuth's The Art of Computer
> Programming, volume 2."
> [sample-size items]
> (let [maybe-insert-item
> (fn [[num current] item]
> (if (< num sample-size)
> [(inc num) (conj current item)]
> (let [index (rand-int num)]
> (if (< index sample-size)
> [(inc num) (assoc current index item)]
> [(inc num) current]))))]
> (second (reduce maybe-insert-item [0 []] items))))
>
> It seems to work fine, but it strikes me as a little busy with ()[],
> even for Lisp. Does anyone have any pointers? Will the internal
> function "maybe-insert-item" be evaluated every time "random-sample"
> is called, and if so, is that worth worrying about wrt. program
> optimization?
>
> Does this sort of thing belong in clojure-contrib or somewhere else?
> It seems awfully short but it's a nice function to have, at least for
> me.
>
> Thanks,
> Steve
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
