Stavros Macrakis a ?crit :
> Appending to the *end* of a list is expensive. Cons'ing on to the
> beginning then reversing is much faster:
>
> (%i1) showtime:all;
> Evaluation took 0.0000 seconds (0.0000 elapsed)
> (%o1) all
> (%i2) (l:[],for i thru 20000 do l:cons(i,l),reverse(l))$
> Evaluation took 0.1000 seconds (0.1000 elapsed)
> (%i3) (l:[],for i thru 20000 do l:append(l,[i]))$
> Evaluation took 4.6300 seconds (4.6300 elapsed)
Thank you, I forgot this big difference. Too bad that the word "append"
is easier to remember for me !
with this improvement, fc computes the list faster than ff2. And two
cents more, notice that the Farey sequence is symmetric around 1/2,
hence it suffices to compute one half of it (only for 2*c<d), then
transform the result by symmetry (faster than computing the other half) :
fc2(n):=block(L:[[0,1]],a:0,b:1,c:1,d:n,
while 2*c<d do
(k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f, L:cons([a,b],L)),
append(reverse(L) , [[1,2]] , map(lambda([x],[x[2]-x[1],x[2]]),L)));
Eric
>
> On Mon, Jun 14, 2010 at 15:55, reyssat <eric.reyssat at math.unicaen.fr
> <mailto:eric.reyssat at math.unicaen.fr>> wrote:
>
> Adam Majewski a ?crit :
>
> ......reyssat pisze:
>
> This is the first method of
> http://magma.maths.usyd.edu.au/magma/Examples/node6.html
> a maxima implementation is :
> fc(n):=block(a:0,b:1,c:1,d:n,
> while c<n do
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f));
>
>
> Thx but fc gives no result. (:-))
>
> Yes, this is why I said the elements are computed but not stored.
>
> One way to get a result is to add a print instruction inside the
> loop :
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f, print([a,b])));
> Of course, printing takes time.
>
> An other way is to store the result, maybe by appending the new
> element :
>
> fc(n):=block(L:[],a:0,b:1,c:1,d:n,
> while c<n do
> (k:floor ((b+n)/d), e:k*c-a,f:k*d-b, a:c,b:d,c:e,d:f,
> L:append(L,[[a,b]])),L);
>
> but I don't know if appending one element each time is efficient
> or not.
>
> Eric
>
>
> Adam
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
>
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu <mailto:Maxima at math.utexas.edu>
> http://www.math.utexas.edu/mailman/listinfo/maxima
>
>