Re: Re: Why these definitions are so slow
- To: mathgroup at smc.vnet.net
- Subject: [mg52196] Re: [mg52160] Re: Why these definitions are so slow
- From: DrBob <drbob at bigfoot.com>
- Date: Sun, 14 Nov 2004 04:31:04 -0500 (EST)
- References: <cn1o84$eov$1@smc.vnet.net> <200411130940.EAA00977@smc.vnet.net>
- Reply-to: drbob at bigfoot.com
- Sender: owner-wri-mathgroup at wolfram.com
Could it be the OP intended Integralas to be additive? If so, this works: ClearAll@Integralas Integralas[b_ c_] := b Integralas@c /; FreeQ[b, rTilde]; Integralas[b_] := b /; FreeQ[b, rTilde]; Integralas[b_ + c_] := Integralas@b + Integralas@c; Bobby On Sat, 13 Nov 2004 04:40:08 -0500 (EST), David Bailey <dave at Remove_Thisdbailey.co.uk> wrote: > 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 > > > > -- DrBob at bigfoot.com www.eclecticdreams.net
- References:
- Re: Why these definitions are so slow
- From: David Bailey <dave@Remove_Thisdbailey.co.uk>
- Re: Why these definitions are so slow