Weighted RNG

Only positive weights allowed

Implementation

Generate Random

Only one random number is required to determine the index of selected label, therefore the approach is a simple algorithm with pseudocode:


                
                    Get total of all weights.
                    Generate a random number between 0 and total of weights.
                    For each label, cumulative sum its weight and check if random number is less than the sum.

The time complexity of this approach is O(n) where n is the number of labels, and the extra space complexity is O(1).

Generate Distribution

10000 is chosen as sample size, but using the same algorithm as above would have a worst case time complexity of O(s*n) where s is the sample size and n is the number of labels. Therefore, a better approach is to accumulate values in an array and perform a binary search for each random number generated.


                
                    Iterate and cumulative sum for each weight, record in array.
                    Generate a random number between 0 and total of weights.
                    Perform binary search on the array of cumulative sums to determine the index of selected label.
                    Repeat step 3 for a total of sample size.

The time complexity of this approach is O(s*log(n)) where s is the sample size and n is the number of labels. The extra space complexity is O(n).