For loop searching takes too long!

[Peter Otten]

elsa wrote:

> Hi guys,
> 
> I've got a problem with my program, in that the code just takes too
> long to run. Here's what I'm doing. If anyone has any tips, they'd be
> much appreciated!
> 
> So, say I have a list of lists that looks something like this (I'm
> using a list of lists, rather than a list of tuples, as I need it to
> be mutable):
> 
> myList = [[786,0],[45, 1],[673,1],...................[23,46]]
> 
> there are enough entries in the outer list, that the sum of myList[i]
> [0] across all i could be as high as 10^7.
> 
> Now, what I need to do is randomly choose one myList[i], however the
> distribution of my random choice needs to be proportional to the
> values of myList[i][0]. So, for this list above, I'd have a much
> higher chance of choosing myList[0] than myList[1].
> 
> Here is how I'm doing it at the moment:
> 
> def chooseI(myList):
> mySum=0
> choice = random.choice(range(1,sum([i[0] for i in myList])+1))
> for i in range(len(myList)):
> mySum+=myList[i][0]
> if mySum>=choice:
> return i
> break
> 
> This works just fine if sum([i[0] for i in myList]) is less than
> 10,000, say. However if its up around 10^7, the whole thing crashes.
> Is there a faster way of doing this, that doesn't involve as many
> computational steps?

Do the first items of the inner lists change often? If not you can put the 
running sum into them, i. e.

myList = [[768, ...], [786+45, ...], [786+45+673, ...], ...]

and use bisect.bisect() to choose the item.

Peter