I have a solution that I've scratched out, but it's a tad messy:
First, let's say we have a random number from a uniform distribution we'll be using to select a random class from a class probability distribution:
r = 0.525325235325
And a list of classes, along with a corresponding list of values representing a class probability distribution for the four classes:
classes = ["w", "x", "y", "z"] distribution = [0.1, 0.2, 0.3, 0.4]
Now, to get the cumulative probabilities:
b = [sum(distribution[0:x + 1]) for x in range(len(distribution))] >>> b [0.1, 0.30000000000000004, 0.6000000000000001, 1.0]
So far so good. Now, select a class by the weighted probability:
c = [y for y in b if y > r] >>> c 0.6000000000000001
And to get the selected class:
selected = classes[b.index(c)] >>> selected 'y'
Putting it all together:
r = 0.525325235325 classes = ["w", "x", "y", "z"] distribution = [0.1, 0.2, 0.3, 0.4] b = [sum(distribution[0:x + 1]) for x in range(len(distribution))] selected = classes[b.index([y for y in b if y > r])]
This works well enough. The thing is, it will be called each time the class probability distribution is updated along with a complex code base – so efficiency matters.
Are there any ways I can make this code more efficient in terms of speed and/or memory usage (eliminating b without the expense of additional processing would be nice) in Python? Alternatively, is there an established algorithm for this problem that I've overlooked?