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