For loop searching takes too long!
__peter__ at web.de
Fri Jan 29 01:41:58 CET 2010
> 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]
>  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]. So, for this list above, I'd have a much
> higher chance of choosing myList than myList.
> Here is how I'm doing it at the moment:
> def chooseI(myList):
> choice = random.choice(range(1,sum([i for i in myList])+1))
> for i in range(len(myList)):
> if mySum>=choice:
> return i
> This works just fine if sum([i 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.
More information about the Python-list