[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

• Follow-Ups:
  • Re: Re: Why these definitions are so slow
    • From: DrBob <drbob@bigfoot.com>