# Still too slow

Alf P. Steinbach alfps at start.no
Sun Jan 31 02:34:24 CET 2010

```* 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
>
>

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

```