Still too slow

[Alf P. Steinbach]

* 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