For loop searching takes too long!
jjposner at optimum.net
Fri Jan 29 01:50:32 CET 2010
On 1/28/2010 6:52 PM, 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]
>  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?
This way of generating *choice* might be less resource-intensive:
list_total = 0
for x in myList:
list_total += x
choice = random.randint(1, list_total)
This avoids creating another list (the list comprehension) as big as myList.
BTW, I don't think you need to *break* after you've already *return*ed.
More information about the Python-list