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
--
http://mail.python.org/mailman/listinfo/python-list
