MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

RE: Re: Redefine[Plus] - problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg41152] RE: [mg41134] Re: Redefine[Plus] - problem
  • From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
  • Date: Tue, 6 May 2003 05:56:19 -0400 (EDT)
  • Sender: owner-wri-mathgroup at wolfram.com

>-----Original Message-----
>From: bobhanlon at aol.com [mailto:bobhanlon at aol.com]
To: mathgroup at smc.vnet.net
>Sent: Monday, May 05, 2003 8:41 AM
>To: mathgroup at smc.vnet.net
>Subject: [mg41152] [mg41134] Re: Redefine[Plus] - problem
>
>
>I do not know the cause of the timing difference other than 
>that you modified the definition of Plus.  
>It is generally a bad idea to modify a built-in
>function.  Rather than modify Plus, set UpValues of fc using TagSet.
>
>Clear[fc];
>fc /: fc[x_]+fc[y_]:=fc[x+y];
>fc /: k_?NumericQ + fc[x_] := fc[k+x];
>
>
>Bob Hanlon
>


>In article <b92ha1$li0$1 at smc.vnet.net>, Petr Kujan 
><kujanp at fel.cvut.cz> wrote:
>
><< 
>Subject:	Redefine[Plus] - problem
>From:		Petr Kujan <kujanp at fel.cvut.cz>
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>Date:		Sun, 4 May 2003 08:00:01 +0000 (UTC)
>
>Hello all,
>
>I would be grateful if someone could explain the difference in
>time consummation.
>
>I need redefine standard function Plus[] for function fc[]:
>
>	Unprotect[Plus];
>	Plus[a : fc[x_], b : fc[y_]] := fc[x + y]
>	Plus[k : _?NumericQ, b : fc[y_]] := fc[k + y]
>	Protect[Plus];
>
>
>Now easy computation is very slow (time consummation is exponential!):
>
>	dat = Table[s, {20}];
>	Plus @@ dat // Timing
>
>	{20.019 Second, 20 s}
>
>
>But if the symbol s replace by x only:
>
>	dat = Table[x, {20}];
>	Plus @@ dat // Timing
>	
>	{0. Second, 20 x}
>
> >><BR><BR>
>


This has nothing to do with Plus in special, but with any symbol having the
attributes Flat, OneIdentity, Orderless. Look at:

In[1]:= Attributes[oops] = {Flat, OneIdentity, Orderless}
Out[1]= {Flat, OneIdentity, Orderless}

In[2]:= oops[_, f[_]] := {}

In[3]:= 
syms = Symbol /@ Characters["abcdefghijklmnopqrstuvwxyz"]
Out[3]=
{a, b, c, d, e, f, g, h, i, j, k, l, m,
 n, o, p, q, r, s, t, u, v, w, x, y, z}

In[4]:= Timing[oops @@ Table[#, {13}]][[1, 1]] & /@ syms
Out[4]=
{0., 0., 0., 0., 0., 0.21, 0., 0., 0., 0., 0., 0., 0.,
 0., 0., 0., 0., 0., 0.201, 0., 0., 0., 0., 0., 0., 0.}

In[5]:=
syms[[#]] & @@@ 
  Position[Timing[oops @@ Table[#, {13}]][[1, 1]] & /@ syms, 
    time_ /; time > .0125]

Out[5]= {f, s}

In[6]:= Quit[]


You see, it's not only s, but also f that has got some problems!


Let's change the definition of oops a little bit:

In[1]:= Attributes[oops] = {Flat, OneIdentity, Orderless}
Out[1]= {Flat, OneIdentity, Orderless}

In[2]:= oops[_, g[_]] := {}

In[3]:=
syms = Symbol /@ Characters["abcdefghijklmnopqrstuvwxyz"]
Out[3]=
{a, b, c, d, e, f, g, h, i, j, k, l, m,
 n, o, p, q, r, s, t, u, v, w, x, y, z}

In[4]:=
Timing[oops @@ Table[#, {13}]][[1, 1]] & /@ syms
Out[4]=
{0., 0., 0., 0., 0., 0., 0.21, 0., 0., 0., 0., 0., 0.,
 0., 0., 0., 0., 0., 0., 0.201, 0., 0., 0., 0., 0.01, 0.}

In[5]:=
syms[[#]] & @@@ 
  Position[Timing[oops @@ Table[#, {13}]][[1, 1]] & /@ syms, 
    time_ /; time > .0125]

Out[5]= {g, t}

In[6]:= Quit[]

Now it's g and t! Perhaps it is easier to understand the cases for f and g
respectively. The problematic definition is 

  oops[_, f[_]] := ....

Now for oops[f, f, f, f, f, ...] f matches to the head of the second
pattern. It doesn't match f[_], but this seems to be sufficient to trigger
searching for all pairs of arguments of the input (due to Orderless
attribute). This clearly takes ~ n! operations, although none succeeds. If
we substitute f for g in the definition, same thing appears to g. 

s is at position position of f + 13, t at position of g + 13 in the
alphabet. If you define for Symbol["a"] you'll also get a problem for
Symbol["n"] etc. So this seems to have something to do with lookup for
symbols or with the internal coding of symbols at least (think of a
compressed bitstring representation). You now may try to spend quite a lot
of time to look for uppercase, and Greek, and script etc.

The search for matching pairs also is triggered when the name of the
function in the definition of oops just begins with that letter (which is no
surprise if there is something with that bitstring hypothesis of mine).

With a definition 

In[2]:= oops[_, _[_]] := {}

of course you are always drawn in to that time consuming search:

In[4]:= Timing[oops @@ Table[#, {13}]][[1, 1]] & /@ syms
Out[4]=
{0.2, 0.211, 0.2, 0.2, 0.201, 0.21, 0.2, 0.21, 0.201, 0.2, 0.2, 0.201, 0.2, 
 0.2, 0.21, 0.201, 0.2, 0.2, 0.201, 0.21, 0.2, 0.201, 0.2, 0.21, 0.2, 0.201}

So much for speculations about the whys. 



The real point to take however, is to recall what is done with a definition
of kind

  oops[_, f[_]] := ....

in conjuction with Orderless attribute (of oops).


--
Hartmut Wolf



  • Prev by Date: Re: How change $AddOnsDirectory
  • Next by Date: Re: How change $AddOnsDirectory
  • Previous by thread: Re: Redefine[Plus] - problem
  • Next by thread: WebMathematica and the Palm handheld