duncan smith wrote:
southof40 wrote:
I have list of of N Vehicle objects - the only possible vehicles are
cars, bikes, trucks.
I want to select an object from the list with a probability of : cars
0.7, bikes 0.3, trucks 0.1.
I've currently implemented this by creating another list in which each
car object from the original list appears 7 times, each bike 3 times
and each truck once. I then pick at random from that list.
This works but seems very clunky to me. Can anyone suggest a better
data structure which would support the 'weighted randomness' I'm
after ?
I'm not fixed on the idea of using a list - could be a dictionary,
tree whatever .
Thanks in advance.
Try googling for "alias table". Efficient if you're selecting many
random objects from the same mass function. Better than binary search
on the cumulative mass function in big-O terms (but maybe not in
practical terms for reasonable sized problems). Neither approach is as
efficient as the one you outlined, but the required list size might be
an issue for some sets of probabilities.
Duncan
BTW, the alias table approach is basically a means of getting round the
problem of needing large lists. Assuming your probabilities should be
0.7, 0.2 and 0.1 you could construct a list of 3 objects. The first
would be 100% car, the second would be 60% bike and 40% car, the third
would be 30% truck and 70% car. Choose an object at random, then the
vehicle type according to the mass function associated with the object.
The alias table approach only requires the generation of a single
uniform random variate and a single comparison (once you've constructed it).
Duncan
--
http://mail.python.org/mailman/listinfo/python-list
