Still too slow

[Dave Angel]

John Posner wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">On 
> 1/30/2010 6:08 PM, elsa wrote:
>> Hello again,
>>
>> 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']]. 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)
>>
>> 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
>>
>> 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,
>>
>> Elsa.
>
> Elsa,
>
> 1. You changed the subject line from "For loop searching takes too 
> long!" to "Still too slow". This causes newsreader programs to start a 
> new discussion thread, which makes life difficult for people who need 
> to refer back to previous messages. Please don't change the subject 
> line any more.
>
> 2. You provided a very clear description of your original question:
>
>   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].
>
> This description should be the doc string for the chooseInd() function 
> -- for example:
>
>   def chooseInd(L,n):
>       """
>       randomly choose one L[i], so that the distribution
>       of choices is proportional to the values of L[i][0]
>       """
>
> It is not clear (to me, anyway) what the other functions are trying to 
> accomplish. So please add a doc string to each of these functions, 
> with descriptions of similar clarity. This will help us a lot. And it 
> will help you, too, if you return to the code after a few 
> days/weeks/months of directing your attention elsewhere.
>
> 3. Please provide a *complete* transcript of an interactive session 
> that exercises this code.
>
> Tx,
> John
>
>
Remarks aimed at elsa, not John.

You used tabs in your source code, which don't survive mail very well.  
So indentation is different in my quoted copy than presumably in your 
original.  No bug there, but I much prefer having my editor expand all 
tabs into spaces (4 colums)

You have a typo in the initialization of L.  Try pasting it from a 
working session, instead of retyping it.  Presumably you wanted
       L= [[100,'NA']].        rather than         [[100],['NA']].
The latter value throws an exception in the code.

You could start simply by changing the values in the event() function.  
No point in returning None half the time when that'll accomplish 
nothing.  So just double the fractions you're checking against, or scale 
the random value.

The pattern produced is interesting.  The only count that gets very big 
is L[0][0]. ("Them what has, gets")   Lots of the other counts reach 
zero, and once they do, they won't ever change.

The algorithm is O(N*N), and it already takes a long time for 10**4.  So 
10**7 would be enormous.

If the improvement needed were minor, you should profile it, figure 
where all the time is spent, and optimize that.  But I think that's 
hopeless with this data structure.

At a guess, I'd think you should build a single list that grows to size 
'limit', where you start with 100 items of value "NA".  No counts 
needed, because they're all implicitly count of 1.  Then write your code 
to manipulate that list.  When you finish, construct the list you really 
want, by using something like the groupby() function.

DaveA