[Date Index]
[Thread Index]
[Author Index]
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
Prev by Date:
**Re: matlab code to mma?**
Next by Date:
**Re: Counting Runs**
Previous by thread:
**Why these definitions are so slow**
Next by thread:
**Re: Re: Why these definitions are so slow**
| |