For loop searching takes too long!

[John Posner]

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]
> [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?
>

This way of generating *choice* might be less resource-intensive:

   list_total = 0
   for x in myList:
       list_total += x[0]
   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.

-John