For loop searching takes too long!

[elsa]

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?

Thanks!

elsa