* 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.
Oh, forgot to add: since your array's first item will be the one that's far most
often chosen a "blind" sort of literal implementation of the above will perhaps
slow down the program instead of speeding it up, because it only speeds up those
searches that progress beyond the first item. But anyway, I'm guessing that
checking the first item first, as a special case, will really improve things.
Only when it turns out that it's not the first item, apply binary search.
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
/s/double/increase/g
'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
--
http://mail.python.org/mailman/listinfo/python-list
