Re: Why these definitions are so slow
- To: mathgroup at smc.vnet.net
- Subject: [mg52160] Re: Why these definitions are so slow
- From: David Bailey <dave at Remove_Thisdbailey.co.uk>
- Date: Sat, 13 Nov 2004 04:40:08 -0500 (EST)
- References: <cn1o84$eov$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Arturas Acus wrote: > Dear Group, > > Could somebody explain why these simple definitions takes so long time > to run? > I also tried to wrap them with HoldPattern[] in various ways, change > blanks, etc., all in vain. > > In[1]= > > Integralas[Times[a__, b_?(FreeQ[#, rTilde] &), c___]] := > b*Integralas[Times[a, c]] > > Integralas[Plus[a__, b_?(FreeQ[#, rTilde] &), c___]] := > b + Integralas[Plus[a, c]] > > Integralas[n_?NumberQ] := n > > > > In[2]= > > Integralas[(3*aTilde)/(4*Pi) + (3*aTilde*j)/(2*Pi) + > (3*aTilde*j^2)/(2*Pi) - (9*aTilde*Cos[2*F[rTilde]])/(8*Pi) + > (3*aTilde*j*Cos[2*F[rTilde]])/(2*Pi) + > (3*aTilde*j^2*Cos[2*F[rTilde]])/(2*Pi) + 3*rTilde^2*Sin[F[rTilde]]^2 - > 4*j*rTilde^2*Sin[F[rTilde]]^2 - 4*j^2*rTilde^2*Sin[F[rTilde]]^2 + > 3*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 - > 4*j*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 - > 4*j^2*rTilde^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^2 - Sin[F[rTilde]]^4 - > 2*j*Sin[F[rTilde]]^4 - 2*j^2*Sin[F[rTilde]]^4 - > 6*rTilde^2*Sin[F[rTilde]]^4 + 8*j*rTilde^2*Sin[F[rTilde]]^4 + > 8*j^2*rTilde^2*Sin[F[rTilde]]^4 + 3*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4 - > 4*j*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4 - > 4*j^2*Cos[2*F[rTilde]]*Sin[F[rTilde]]^4] > > In[4]:= > $Version > > Out[4]= > 5.0 for Linux (November 18, 2003) > > > Sincerely, Arturas Acus > > Hi, That definition is spectacularly slow, and it was quite interesting to figure out why! The first thing to realise is that the Mathematica pattern matcher already takes into account the fact that Plus and Times commute, so you can improve the efficiency quite a bit thus: Integralas[ b_?(FreeQ[#1, rTilde] &) c_] := b Integralas[c]; Integralas[b_?(FreeQ[#1, rTilde] &) + c_] := b + Integralas[c]; Integralas[n_?NumberQ] := n; However, even this version runs pretty slow, so I changed the definition to this: freer[x_] := (Print[freer[x] // HoldForm]; FreeQ[x, rTilde]); Integralas[ b_?freer c_] := b Integralas[c]; Integralas[b_?freer + c_] := b + Integralas[c]; Integralas[n_?NumberQ] := n; I also used a variant where I counted the calls to freer, rather than printing them out. This shows that freer (i.e. FreeQ) is called 2.3 x 10^6 times. It was probably called many more times in your original version. The problem is that a pattern like Plus[a_,b_] can match a sum of 20 odd terms in an enormous number (2^20-2) of ways. This is compounded by the fact that Mathematica rearranges the pattern b_?freer + c_ into c_ +b_?freer (because they commute and happen to sort that way!) This means that if you give it a complicated sum at the start c gets set to each term in turn and b gets set to the rest - there is a fair combinatorial explosion here and the case of interest is near the end. You can avoid the rearrangement using HoldPattern, but perhaps it is easier to rearrange your definition thus: Integralas[ b_ c_] := b Integralas[c] /; FreeQ[b, rTilde]; Integralas[b_ + c_] := b + Integralas[c] /; FreeQ[b, rTilde]; Integralas[n_?NumberQ] := n; Tests are generally more efficient within patterns than placed at the end, but b_ c_ does not get sorted into c_ b_, so the search finds a match much sooner. Of course, when Integrelas gets an expression that it can't simplify you still have to go through all possibilities - so it is still not super efficient - but this version only takes 4.6 secs on my 2GHz machine. You could improve the efficiency more, but I suspect this is a cut-down of your real problem, so I don't want to complicate the code. The following illustrates the combinatorial explosion of matching: Foo[a_ + b_] := 0 /; (Print[a]; False); Foo[a+b+c+d] Regards, David Bailey
- Follow-Ups:
- Re: Re: Why these definitions are so slow
- From: DrBob <drbob@bigfoot.com>
- Re: Re: Why these definitions are so slow