On Wed, May 13, 2009 at 03:50:37PM -0500, Barton Willis wrote:
> For a 20,000 member list, my function bob is about 100
> times faster than your function rcs. For longer lists,
> the gap increases (rcs is O(n^2) and bob is O(n)).
>
> (%i1) bob(l) := block([s : 0, k : 1],
> for lk in l do (
> s : s + binomial(lk-1,k),
> k : k + 1),
> s + 1)$
> (%i2) rcs(S) := block([L : listify(S)],
> apply("+",create_list(binomial(L[i]-1,i), i,1,length(L))) + 1)$
> (%i3) load("integer_sequence")$
>
> (%i27) p : 1 .. 2 * 10^4$
> Evaluation took 0.0500 seconds (0.0500 elapsed)
> (%i21) showtime : all$
>
> Evaluation took 0.0000 seconds (0.0000 elapsed)
> (%i28) bob(p);
> Evaluation took 0.2700 seconds (0.2700 elapsed)
>
> (%o28) 1
> (%i29) rcs(p);
>
> Evaluation took 29.3300 seconds (29.3300 elapsed)
> (%o29) 1
>
That's funny that somehow in this special case (where all
summands are 0) Maxima apparently shows some intelligence.
But in general summing over a list is faster than using
a loop, even if all summands are 0:
apply("+",create_list(0,i,1,1000000));
Evaluation took 1.4880 seconds (1.5000 elapsed)
0
block([s : 0], for i : 1 thru 1000000 do s : s + 0, s);
Evaluation took 22.1250 seconds (22.2610 elapsed)
0
block([s : 0], for i in (1 .. 1000000) do s : s + 0, s);
Evaluation took 11.9130 seconds (12.6750 elapsed)
0
block([s : 0], for i in create_list(i,i,1,1000000) do s : s + 0, s);
Evaluation took 10.5200 seconds (11.2000 elapsed)
0
One sees that "listification" speeds up things.
Btw, apparently the list-creation via .. is not as
efficient as it could be:
p : create_list(i,i,1,1000000)$
Evaluation took 0.9640 seconds (0.9610 elapsed)
p : 1 .. 1000000$
Evaluation took 2.3720 seconds (2.4340 elapsed)
Back to the main subject, comparing bob and rcs:
As soon as the summands are not zero, rcs is always
a bit faster than bob (but that's negligible, it's just
that the summation is a bit faster, while this is
negligible compared to the computation of binomial):
S : create_list(i,i,500,1500)$
Evaluation took 0.0000 seconds (0.0010 elapsed)
bob(S);
Evaluation took 3.3440 seconds (3.4850 elapsed)
48956300222189270646557113925193925652940423369850040531677455671007891415747618188744790931775904165360021652735982071743256539502580686357834778033375105732021891793956694929082893229557737271650990089542008098142293886148106609952240556364231670608192414563263405438846371339910702793947099334867973876957660313608853976572729634187362371903306673828221596229395273825223900422561108859307534931529221600560000
rcs(setify(S));
Evaluation took 3.2840 seconds (3.4100 elapsed)
48956300222189270646557113925193925652940423369850040531677455671007891415747618188744790931775904165360021652735982071743256539502580686357834778033375105732021891793956694929082893229557737271650990089542008098142293886148106609952240556364231670608192414563263405438846371339910702793947099334867973876957660313608853976572729634187362371903306673828221596229395273825223900422561108859307534931529221600560000
Back to the special 0-case
bob(l) := block([s:0,k:1],for lk in l do (s:s+binomial(lk-1,k), k:k+1), s+1)$
rcs(S) := block([L:listify(S)], apply("+",create_list(binomial(L[i]-1,i), i,1,length(L))) + 1)$
bob(create_list(i,i,1,100000));
Evaluation took 3.2880 seconds (3.4240 elapsed)
1
rcs(create_list(i,i,1,100000));
Evaluation took 121.4910 seconds (130.3950 elapsed)
1
bob(create_list(i,i,2,100000));
Evaluation took 3.1930 seconds (3.3040 elapsed)
100000
rcs(create_list(i,i,2,100000));
Evaluation took 120.2910 seconds (131.4270 elapsed)
100000
bob(create_list(i,i,10,100000));
Evaluation took 7.6770 seconds (8.1210 elapsed)
2754740009356989154770920739977138900000
rcs(create_list(i,i,10,100000));
Evaluation took 131.2560 seconds (141.3050 elapsed)
2754740009356989154770920739977138900000
(%i12) bob(create_list(i,i,20,100000));
Evaluation took 13.1290 seconds (14.1560 elapsed)
(%o12) 820658910701960823288629619083493757353632408085054289607074287128597032900000
(%i11) rcs(create_list(i,i,20,100000));
Evaluation took 144.2290 seconds (154.9410 elapsed)
(%o11) 820658910701960823288629619083493757353632408085054289607074287128597032900000
Likely the weakness is the quadratic effort for evaluating the L[i] !
So forget what I said above (but I leave it for "pedagogical reasons"): the truth should
be that regarding computation of binomial coefficients both functions have exactly the
same effort, while rcs is faster with the pure summation, but pays heavily for index
access.
rcs2(S) := block([L:listify(S)], apply("+", map(binomial,L-1,create_list(i,i,1,length(L))))+1)$
rcs2(create_list(i,i,1,100000));
Evaluation took 1.3720 seconds (1.4030 elapsed)
1
rcs2(create_list(i,i,2,100000));
Evaluation took 1.2960 seconds (1.2980 elapsed)
100000
rcs2(create_list(i,i,10,100000));
Evaluation took 5.0570 seconds (8.5100 elapsed)
2754740009356989154770920739977138900000
That's the current speed-champion. And I also think that it expresses the content nicely.
Actually, that's also the form I generally promote in my "OKlibrary" (at least for my students ;-)),
since in my experience it's always fastest, and in this case, since the list is given anyway,
it only uses moderate space (compared what already is used). But for that given special case
I was actually anticipating only lists of length, say, 10.
Oliver
>
>
> >Forgot?to?reply?to?the?whole?list;?here?is?my?answer.
> >
> >>?On?Wed,?May?13,?2009?at?02:00:30PM?-0500,?Barton?Willis?wrote:
> >>?(1)?If?there?is?a?global?hashed?array?L?defined,?L[i]?extracts?the?value
> >of
> >>?the
> >>?global?hashed?array,?not?the?member?of?local?list?variable?L.?The?fix?is
> >to
> >>?replace?L[i]?with?inpart(L,i).
> >>
> >
> >I'll?keep?that?in?mind.
> >
> >>?(2)?Your?code?is?inefficient,?I?think.?Try?rewriting?rcs?as?loop:
> >>
> >>?(%i16)?bob(l)?:=?block([s?:?0,?k?:?1],
> >>???for?lk?in?l?do?(
> >>??????s?:?s?+?binomial(lk-1,k),
> >>??????k?:?k?+?1),
> >>???s?+?1)$
> >>
> >>?(%i28)?bob([a,b]);
> >>?(%o28)?((b-2)*(b-1))/2+a
> >
> >It's?really?the?opposite:?Loops?are?*much*?slower!
> >
> >?(%i13)?block([s:0],?for?i?from?1?thru?1000000?do?s?:?s?+?i,?s);
> >Evaluation?took?21.9220?seconds?(42.0870?elapsed)
> >(%o13)?500000500000
> >(%i14)?apply("+",create_list(i,i,1,1000000));
> >Evaluation?took?1.4680?seconds?(1.4670?elapsed)
> >(%o14)?500000500000
> >
> >(And?this?becomes?worse?for?longer?loops;?of?course,?at?some
> >point?memory?doesn't?follow?;-()
> >
> >>?(3)?The?usage?of?a?Maxima?set?as?an?input?to?rcs?seems?spurious.
> >>
> >
> >sure?---?this?comes?from?the?context?where?this?is?all?used.
> >
> >>?(4)?As?for?the?calls?to?ev?in?your?code,?I?don't?want?to?think?about?it.
> >>?Ev?makes?my?head?hurt.
> >>
> >
> >But?it?seems?to?be?the?only?possibility?in?this?application?
> >
> >thanks!
> >
> >Oliver
> >
> >>?>?Barton
> >>?>
> >>?>?-----maxima-bounces at math.utexas.edu?wrote:?-----
> >>?>
> >>?>
> >>?>?>Maxima?5.18.1?http://maxima.sourceforge.net
> >>?>?>Using?Lisp?ECL?9.4.1
> >>?>?>declare(rv,noun)$
> >>?>?>rcs(S)?:=?block([L?:?listify(S)],
> >>?>?>??apply("+",create_list(binomial(L[i]-1,i),?i,1,length(L)))?+?1)$
> >>?>?>(%i4)?ev(rv(1,4),rv([L]):=rcs(setify(L)),nouns);
> >>?>?>(%o4)?4
> >>?>?>(%i5)?ev(rv(1,5),rv([L]):=rcs(setify(L)),nouns);
> >>?>?>(%o5)?7.0
> >>?>?>(%i6)?rcs({1,5});
> >>?>?>(%o6)?7
> >>?>?>
> >>?>?>I?hope?you?see?the?disaster:?o6?is?correct,?and?should?be?the?same
> >>?>?>as?o5,?but?somehow?suddenly?the?result?is?turned?into?a
> >floating-point
> >>?>?>number?(which?depends?on?the?values?---?doesn't?happen?with?o4).
> >>?>?>
> >>?>?>I?guess?I?should?submit?this?as?a?bug,?but?wanted?to?hear?some
> >comments
> >>?>?>first.
> >>?>?>
> >>?>?>(Workarounds??Currently?the?above?behaviour?blocks?a?whole
> >development;
> >>?>?>but
> >>?>?>using?floor?doesn't?seem?safe?...)
> >>?>?>
> >>?>?>Oliver
> >>?>?>
> >>?>?>_______________________________________________
> >>?>?>Maxima?mailing?list
> >>?>?>Maxima at math.utexas.edu
> >>?>?>http://www.math.utexas.edu/mailman/listinfo/maxima
> >>
> >>?--
> >>?Dr.?Oliver?Kullmann
> >>?Computer?Science?Department
> >>?Swansea?University
> >>?Faraday?Building,?Singleton?Park
> >>?Swansea?SA2?8PP,?UK
> >>?http://cs.swan.ac.uk/~csoliver/
> >
> >--
> >Dr.?Oliver?Kullmann
> >Computer?Science?Department
> >Swansea?University
> >Faraday?Building,?Singleton?Park
> >Swansea?SA2?8PP,?UK
> >http://cs.swan.ac.uk/~csoliver/
> >_______________________________________________
> >Maxima?mailing?list
> >Maxima at math.utexas.edu
> >http://www.math.utexas.edu/mailman/listinfo/maxima
--
Dr. Oliver Kullmann
Computer Science Department
Swansea University
Faraday Building, Singleton Park
Swansea SA2 8PP, UK
http://cs.swan.ac.uk/~csoliver/