Still too slow

[Alf P. Steinbach]

* elsa:
> 
> Thanks for the tips r.e random.ranint(). This improved matters
> somewhat, however my program is still too slow. If anyone has any
> further tips on how to speed it up, they would be much appreciated!
> 
> So, I'm calling evolve(L,limit) from the interactive prompt. L is
> initally [[100],['NA']].

This would produce an unhandled exception since your code tries to compute the 
sum of the values in the list. You can't add strings and numbers.


> Ideally limit would be 10^7.
> 
> Here is my program:
> 
> import random
> n=100
> 
> def evolve(L,limit):
> 	global n
> 	while n<limit:
> 		evnt = event()
> 		if evnt!="None":
> 			ind = chooseInd(L,n)
> 			action(evnt,L,ind)
> 
> def chooseInd(L,n):
> 	choiceSum=0
> 	index=0
> 	choice = random.randint(1,n)
> 	while choiceSum < choice:
> 		choiceSum+=L[index][0]
> 		index +=1
> 	return (index-1)

This is the problematic part of your program, because it uses time linear in the 
length of L.

Consider if you know the sum s_low of the lower half of the array, and the sum 
s_high of the higher half of the array. Then you can choose the lower half with 
probability s_low/(s_low+s_high), otherwise the higher half. Then repeat this 
recursively for the half chosen, until you get down to a single array element.

This requires keeping track of the sums of halfs of the array, e.g. in a tree 
like structure or a set of arrays of diminishing lengths. Generally it will use 
some constant factor times twice the storage that you're now using. But it 
reduces the time for choosing an index from O(n) to O(log n).

For example, if you have a logical structure like

            *
           / \
          *   1
         / \
        98  1

then at the top level * you choose the left branch with probability 99/(99+1) = 
99/100 = 0.99. At the second level * you choose the right branch with 
probability 1/(98+1) = 1/99. The combined probability of choosing that lower 1 
is then 0.99*(1/99) = 0.01, as it should be.


> def event():
> 	choice = random.random()
> 	if choice <= .3:
> 		event='b'
> 	elif choice <= .4:
> 		event ='d'
> 	elif choice<= .5:
> 		event = 'm'
> 	else:
> 		event = 'None'
> 	return event

Note that you can double the speed of your program by removing the 'None' value. 
Adjust the limits you're checking against so as to retain the same probabilities 
of the choices. Further constant factor speedup is possible by simply returning 
a function to Do Stuff instead of returning a character saying what to do.



> def action(event, L, index):
> 	global n
> 	if event == 'b':
> 		L[index][0]+=1
> 		n +=1
> 	elif event == 'd':
> 		L[index][0]-=1
> 		n -=1
> 	elif event == 'm':
> 		L.append([1,index])
> 		n +=1
> 
> 
> thanks in advance,

An observation about design: you have a global n (the current total sum) and an 
array L that you're passing around everywhere, so that it's effectively also a 
global. This indicates that they should ideally instead be attributes of an 
object, with your routines above as methods. However in Python this may cause 
some overhead, so, perhaps first make it Work (and then make a Copy). :-)


Cheers & hth.,

- Alf