StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The following is a description of random weighted selection of an element of a set (or multiset, if repeats are allowed), both with and without replacement in O(n) space and O(log n) time.</p> <p>It consists of implementing a binary search tree, sorted by the elements to be selected, where each <em>node</em> of the tree contains:</p> <ol> <li>the element itself (<em>element</em>)</li> <li>the un-normalized weight of the element (<em>elementweight</em>), and</li> <li>the sum of all the un-normalized weights of the left-child node and all of its children (<em>leftbranchweight</em>).</li> <li>the sum of all the un-normalized weights of the right-child node and all of its chilren (<em>rightbranchweight</em>).</li> </ol> <p>Then we randomly select an element from the BST by descending down the tree. A rough description of the algorithm follows. The algorithm is given a <em>node</em> of the tree. Then the values of <em>leftbranchweight</em>, <em>rightbranchweight</em>, and <em>elementweight</em> of <em>node</em> is summed, and the weights are divided by this sum, resulting in the values <em>leftbranchprobability</em>, <em>rightbranchprobability</em>, and <em>elementprobability</em>, respectively. Then a random number between 0 and 1 (<em>randomnumber</em>) is obtained.</p> <ul> <li>if the number is less than <em>elementprobability</em>, <ul> <li>remove the element from the BST as normal, updating <em>leftbranchweight</em> and <em>rightbranchweight</em> of all the necessary nodes, and return the element.</li> </ul></li> <li>else if the number is less than (<em>elementprobability</em> + <em>leftbranchweight</em>) <ul> <li>recurse on <em>leftchild</em> (run the algorithm using <em>leftchild</em> as <em>node</em>)</li> </ul></li> <li>else <ul> <li>recurse on <em>rightchild</em></li> </ul></li> </ul> <p>When we finally find, using these weights, which element is to be returned, we either simply return it (with replacement) or we remove it and update relevant weights in the tree (without replacement).</p> <p>DISCLAIMER: The algorithm is rough, and a treatise on the proper implementation of a BST is not attempted here; rather, it is hoped that this answer will help those who <em>really</em> need fast weighted selection without replacement (like I do).</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