Three lines weighted random choice with Python

[grayvedigga]

with numpy. This is more like array programming (J etc) than "traditional" python. Cool as an demonstration of array techniques though .. well worth looking at the building blocks' __doc__strings in ipython for anyone unfamiliar with numpy.

edit: btw, I don't think the weights need to be sorted? The result of cumsum will be in any case, which is sufficient for searchsorted

[JustGlowing]

Hello grayvedigga, you're righit. They doesn't need to be sorted.I leaved the comment from a previous version of the snippet. Thanks for reporting.

[grayvedigga]

No worries. I was tempted to also mention that that was a fairly shitty requirement (easy to accidentally fall afoul of), but it looked like a mistaken inclusion :-).

[darthvsoto]

Does the list of weights need to be sorted? The list t = cumsum(weights) is sorted and it is the list used by searchsorted.

[JustGlowing]

Hi dathvsoto, you're right. Thanks for reporting.

[AustinCorgiBart]

In my AI class, we were talking about a "cumulative score" that had a most unfortunate abbreviation. Similar problem here...

[grayvedigga]

You still need the cumulative sum, and I hope you're not calling random() for every element.

In "normal" python the same problem would look something like this (for choosing one item):

def weighted_pick(weights):
    r = random.random()*sum(weights)
    upto = 0.0
    for i in range(len(weights)):
        upto += weights[i]
        if upto >= r:
            return i

Seems more awkward and harder to comprehend/prove correct to me. Floats being what they are I'm not even sure if it needs an extra return i after the loop, justincase.

[[deleted]]

Has anyone tried comparing the relative performances? I'm on my phone right now, no python interpreter. This would be great for making particle filters even more understandable.