StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSelect random element from a set, faster than linear time (Haskell)
text
Body
copied!<p>I'd like to create this function, which selects a random element from a <a href="http://hackage.haskell.org/packages/archive/containers/latest/doc/html/Data-Set.html#t:Set" rel="nofollow noreferrer">Set</a>:</p> <pre><code>randElem :: (RandomGen g) => Set a -> g -> (a, g) </code></pre> <p>Simple listy implementations can be written. For example (code updated, verified working):</p> <pre><code>import Data.Set as Set import System.Random (getStdGen, randomR, RandomGen) randElem :: (RandomGen g) => Set a -> g -> (a, g) randElem s g = (Set.toList s !! n, g') where (n, g') = randomR (0, Set.size s - 1) g -- simple test drive main = do g <- getStdGen print . fst $ randElem s g where s = Set.fromList [1,3,5,7,9] </code></pre> <p>But using <code>!!</code> incurs a linear lookup cost for large (randomly selected) <code>n</code>. Is there a faster way to select a random element in a Set? Ideally, repeated random selections should produce a uniform distribution over all options, meaning it does not prefer some elements over others.</p> <hr> <p><strong>Edit</strong>: some great ideas are popping up in the answers, so I just wanted to throw a couple more clarifications on what exactly I'm looking for. I asked this question with Sets as the solution to <a href="https://stackoverflow.com/questions/7342862/growing-arrays-in-haskell">this situation</a> in mind. I'll prefer answers that both</p> <ol> <li>avoid using any outside-the-function bookkeeping beyond the Set's internals, and</li> <li>maintain good performance (better than <em>O(n)</em> on average) even though the function is only used once per unique set.</li> </ol> <p>I also have this love of working code, so expect (at minimum) a +1 from me if your answer includes a working solution.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload