ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 23 Apr 2015 16:46:24 -0500Loops get slower as they runhttp://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/Hello,
I am trying to run a simulation in sage as part of my homework. The simulation itself is pretty fast and working fine.
The problem starts when i try to run the simulation several times in a loop, then sage becomes incredibly slow in each repeat.
The program I wrote:
def poisson(lmu):
var('mu n')
g(mu,n)=(e^-mu * mu^n)/factorial(n)
num=random()
sum=g(lmu,0)
for i in xrange(1000):
if num<sum:
return i-1
else:
sum=sum+g(lmu,i)
def galtonwatson(mu,s,gens):
deaths=0
for i in range (gens):
N=1
n=0
while n<s and N!=0:
N=poisson(N*mu)
n=n+1
if N==0:
deaths=deaths+1
return (deaths/gens).N()
both of the functions works fine, then telling sage to fill a list of 10 arrays with the values, and checking how much time it took for each repeat:
L=np.array([[0,0]for i in range(9)])
for i in xrange (9):
t=time.time()
print i
L[i]= (i,galtonwatson(2,i,100))
print (time.time()-t)
Sage output is:
0
0.000202894210815
1
0.393799066544
2
0.893945932388
3
1.54169392586
4
2.87310600281
5
4.84653711319
6
9.23449707031
7
18.3007540703
8
35.5397469997
It ain't the first time that sage loops becomes slower and slower on the run, and I could'nt understand the reason when searching the net.
Thanks in advanced,
David
Wed, 07 Jan 2015 05:01:41 -0600http://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/Answer by tmonteil for <p>Hello,
I am trying to run a simulation in sage as part of my homework. The simulation itself is pretty fast and working fine.
The problem starts when i try to run the simulation several times in a loop, then sage becomes incredibly slow in each repeat.</p>
<p>The program I wrote:</p>
<pre><code>def poisson(lmu):
var('mu n')
g(mu,n)=(e^-mu * mu^n)/factorial(n)
num=random()
sum=g(lmu,0)
for i in xrange(1000):
if num<sum:
return i-1
else:
sum=sum+g(lmu,i)
def galtonwatson(mu,s,gens):
deaths=0
for i in range (gens):
N=1
n=0
while n<s and N!=0:
N=poisson(N*mu)
n=n+1
if N==0:
deaths=deaths+1
return (deaths/gens).N()
</code></pre>
<p>both of the functions works fine, then telling sage to fill a list of 10 arrays with the values, and checking how much time it took for each repeat:</p>
<pre><code>L=np.array([[0,0]for i in range(9)])
for i in xrange (9):
t=time.time()
print i
L[i]= (i,galtonwatson(2,i,100))
print (time.time()-t)
</code></pre>
<p>Sage output is:</p>
<pre><code>0
0.000202894210815
1
0.393799066544
2
0.893945932388
3
1.54169392586
4
2.87310600281
5
4.84653711319
6
9.23449707031
7
18.3007540703
8
35.5397469997
</code></pre>
<p>It ain't the first time that sage loops becomes slower and slower on the run, and I could'nt understand the reason when searching the net.</p>
<p>Thanks in advanced,
David</p>
http://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/?answer=25425#post-id-25425There are (at least) two reasons why your computations get slower when `i` increases.
First, in the `galtonwatson` function, the `while` loops is basically run `i` times. For example, you can `print i,n` after leaving the `while` loop to see this. So of course the bigger `i` is, the more computation there will be. But this only explains a linear grow in the time of your computation.
Second, when you write `g(mu,n)=(e^-mu * mu^n)/factorial(n)` in the `poisson` function, you define a symbolic expression, hence the variable `sum` is also a symbolic expression. The size of this expression can (and actually does) grow with your computation. If you add a `print sum` in your first function just before returning `i-1`, you will see that it starts with small expressions such as `14*e^(-4)`, but when the number `i` of loops increases, `N` also increases so that `poisson()` gets huge entries and has to deal with long symbolic expression, that require more work to be dealt with (comparisons and additions in your case). For example at some point in your computation, the poisson function has to deal with expressions like `2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204)` and it gets even worse after that.
The same issue appears with rational numbers: they do not have a constant size, so it is likely that iterated computation will lead to rationals with bigger and bigger numerators and denominators. If you want to avoid such explosion of the size of the data that you manipulate, you can work with floating point numbers instead, since those keep constant size along the computation.
sage: a
2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204)
sage: RDF(a)
0.9124252826570382
Wed, 07 Jan 2015 09:30:50 -0600http://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/?answer=25425#post-id-25425Comment by OaaH for <p>There are (at least) two reasons why your computations get slower when <code>i</code> increases.</p>
<p>First, in the <code>galtonwatson</code> function, the <code>while</code> loops is basically run <code>i</code> times. For example, you can <code>print i,n</code> after leaving the <code>while</code> loop to see this. So of course the bigger <code>i</code> is, the more computation there will be. But this only explains a linear grow in the time of your computation.</p>
<p>Second, when you write <code>g(mu,n)=(e^-mu * mu^n)/factorial(n)</code> in the <code>poisson</code> function, you define a symbolic expression, hence the variable <code>sum</code> is also a symbolic expression. The size of this expression can (and actually does) grow with your computation. If you add a <code>print sum</code> in your first function just before returning <code>i-1</code>, you will see that it starts with small expressions such as <code>14*e^(-4)</code>, but when the number <code>i</code> of loops increases, <code>N</code> also increases so that <code>poisson()</code> gets huge entries and has to deal with long symbolic expression, that require more work to be dealt with (comparisons and additions in your case). For example at some point in your computation, the poisson function has to deal with expressions like <code>2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204)</code> and it gets even worse after that.</p>
<p>The same issue appears with rational numbers: they do not have a constant size, so it is likely that iterated computation will lead to rationals with bigger and bigger numerators and denominators. If you want to avoid such explosion of the size of the data that you manipulate, you can work with floating point numbers instead, since those keep constant size along the computation.</p>
<pre><code>sage: a
2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204)
sage: RDF(a)
0.9124252826570382
</code></pre>
http://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/?comment=26631#post-id-26631Thank you very much! I did learnt a lot from your answer =]
Sorry for the late response to your answer, actually I just now realized that i forgot to reply earlierThu, 23 Apr 2015 16:46:24 -0500http://ask.sagemath.org/question/25422/loops-get-slower-as-they-run/?comment=26631#post-id-26631