How to Perform Weighted Random Selection with Replacement Efficiently?

Weighted Random Selection with and Without Replacement

Selecting random elements from a list with or without replacement is a common task in programming. While there are established methods for unweighted selection and weighted selection without replacement, selecting weighted elements with replacement poses a unique challenge.

Alias Method for Weighted Selection with Replacement

One of the most efficient approaches for this scenario is the Alias Method. It involves creating equal-sized bins that efficiently represent the weighted list.

Implementation Steps:

1. Normalize weights: Adjust weights so they sum to 1.0, representing selection probabilities.
2. Create partitions: Determine the smallest power of 2 greater than the number of elements and create that many partitions.
3. Assign weights: Place the element with the smallest weight in an empty partition, filling it as much as possible.
4. Fill partitions: If a partition is not full, add the element with the highest weight to fill the remaining space.
5. Repeat: Keep assigning weights until all elements are accounted for.

Runtime Selection:

1. Generate a random number between 0 and 1.
2. Bit-shift the number by the logarithm of the number of partitions (assuming bit-shifting is fast on your platform).
3. If the partition is split, use the decimal portion of the shifted number to decide which element to select.

Advantages of the Alias Method:

• Fast and efficient selection with replacement.
• Avoids the reservoir method for large selections.
• Simple to implement and memory efficient.

The above is the detailed content of How to Perform Weighted Random Selection with Replacement Efficiently?. For more information, please follow other related articles on the PHP Chinese website!