StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's an idea: You could do interval bisection.</p> <ol> <li><code>size s</code> is constant time. Use <code>randomR</code> to get how far into the set you are selecting.</li> <li>Do <code>split</code> with various values between the original <code>findMin</code> and <code>findMax</code> until you get the element at the position you want. If you really fear that the set is made up say of reals and is extremely tightly clustered, you can recompute <code>findMin</code> and <code>findMax</code> each time to guarantee knocking off some elements each time.</li> </ol> <p>The performance would be O(n log n), basically no worse than your current solution, but with only rather weak conditions to the effect that the set not be entirely clustered round some accumulation point, the average performance should be ~((logn)^2), which is fairly constant. If it's a set of integers, you get O(log n * log m), where m is the initial range of the set; it's only reals that could cause really nasty performance in an interval bisection (or other data types whose order-type has accumulation points).</p> <p>PS. This produces a perfectly even distribution, as long as watching for off-by-ones to make sure it's possible to get the elements at the top and bottom.</p> <h2>Edit: added 'code'</h2> <p>Some inelegant, unchecked (pseudo?) code. No compiler on my current machine to smoke test, possibility of off-by-ones, and could probably be done with fewer <code>if</code>s. One thing: check out how <code>mid</code> is generated; it'll need some tweaking depending on whether you are looking for something that works with sets of ints or reals (interval bisection is inherently topological, and oughtn't to work quite the same for sets with different topologies).</p> <pre><code>import Data.Set as Set import System.Random (getStdGen, randomR, RandomGen) getNth (s, n) = if n = 0 then (Set.findMin s) else if n + 1 = Set.size s then Set.findMax s else if n < Set.size bott then getNth (bott, n) else if pres and Set.size bott = n then n else if pres then getNth (top, n - Set.size bott - 1) else getNth (top, n - Set.size) where mid = ((Set.findMax s) - (Set.findMin s)) /2 + (Set.findMin s) (bott, pres, top) = (splitMember mid s) randElem s g = (getNth(s, n), g') where (n, g') = randomR (0, Set.size s - 1) g </code></pre>

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