> How can I efficiently pick a random element from a sorted-set?
If your sorted set is densely packed (if most possible values do appear in the set), then you could just pick a random value, see if it's in the set, and repeat until you find a match.
Otherwise, you could use a sorted-vector. I don't know if there's a good implementation out there, though, so you might have to roll your own.
Or you could use a sorted-set that can do a "random binary search", where it chooses between the first and second halves at random rather than by comparison with a particular value. Maybe you could subclass the Clojure sorted-set to do this, though I'm guessing it's not made for subclassing.
Try just getting the value with rand-int directly. The sorted-set uses
a tree map underneath, so look up time is consistent with a map. Also,
count is O(1).
(get foo (rand-int (count foo)))
This will replace an O(n) call to "nth" with an O(n) call to copy into
a vector, so still leaving me with O(n).