On Sep 26, 2:12 pm, Paul Richards <[email protected]> wrote:
> On Sep 26, 2:12 pm, Paul Richards <[email protected]> wrote:
>
> > Hi,
> > How can I efficiently pick a random element from a sorted-set?
>
> I've come up with a bit of a hack, which relies on me not caring about
> non-uniform distributions. If I create a custom comparator with a
> "random" backdoor, I can select random elements from the sorted set:
>
> (defn my-comp [a b]
> (if (or (= :random a) (= :random b))
> (- (* 2 (rand-int 2)) 1)
> (compare a b)))
>
> ; Create test collection (of strings) using the special comparator
> (def coll (apply sorted-set-by my-comp (map str (range 1 1000))))
>
> (map #(first (subseq coll > %)) ["500" "200" "700" :random :random])
> ; Result: ("501" "201" "701" "626" "286")
>
> Bonus question.. What is the distribution of the random selection?
>
> (I suspect elements will be chosen with some probability like (1/2)^H
> (where H is the height of the element within the red-black tree). I
> should probably generate a histogram to find out..)
I think it's complicated by what you expect "chosen" to mean. If you
were randomly selecting a single element, you would only ever choose
one at the bottom of the tree; the internal nodes would never be
selected, right? Of course, you can't do that, since `get` does an
equality check before returning the item. And if you're selecting a
subseq, it depends on what test(s) you supply, and how many items you
take, and...
Anyway, this is sorta fun to generalize to wrap any other comparator:
(defn hackable-comparator [f]
(fn [& xs]
(if (some #{:random} xs)
(- (* 2 (rand-int 2)) 1)
(apply f xs))))
(def my-comp (hackable-comparator compare))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
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
