Re: Redefine[Plus] - problem
- To: mathgroup at smc.vnet.net
- Subject: [mg41171] Re: Redefine[Plus] - problem
- From: "Carl K. Woll" <carlw at u.washington.edu>
- Date: Tue, 6 May 2003 06:02:14 -0400 (EDT)
- Organization: University of Washington
- References: <b92ha1$li0$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Petr,
As mentioned by others, in general it is not a good idea to write rules for
Plus. Since Plus is an extremely common operation, writing rules for Plus
will slow it down. Moreover, Plus is a Flat, Orderless function, and writing
rules for Flat, Orderless functions needs to be done very carefully.
You might ask why one should be careful when writing rules for Flat,
Orderless functions. In particular, consider the following case of a binary
rule for a Flat, Orderless function f:
SetAttributes[f, {Flat, Orderless}]
f[a_,a_]:= a
Admittedly this definition is silly, since it would be much simpler to
simply use Union. At any rate, when f is applied to a list of random
integers, what will happen? If f were simply flat, then f would compare all
adjacent elements to see if they are the same, and then basically delete one
of them, an O(n) operation, where n is the length of the list. Now consider
the case where f is both flat and orderless. At the minimum, f would need to
compare each element to every other element for an O(n^2) operation.
However, it might be worse than this, since the orderless function means
that all n! permutations of the list are equivalent, and so Mathematica
could basically permute the list, compare adjacent elements and repeat up to
n! times for a complexity of O(n*n!). Since the complexity of the Union
function is O(n log n), the above approach is a horrifyingly awful
possibility.
Consider the following test of the function f:
In[10]:=
Table[f@@Range[i];//Timing,{i,15}]
Out[10]=
{{0. Second, Null}, {0. Second, Null}, {0. Second, Null}, {0. Second,
Null}, {0. Second, Null}, {0. Second, Null}, {0. Second,
Null}, {0. Second, Null}, {0.031 Second, Null}, {0.094 Second,
Null}, {0.234 Second, Null}, {0.734 Second, Null}, {2.266 Second,
Null}, {6.781 Second, Null}, {20.547 Second, Null}}
When f is applied to Range[i], nothing happens other than substituting List
with f, since the input is already sorted and contains no duplicates. Yet
the complexity of this operation appears to be O(3^n), incredibly worse than
O(n log n).
The message you should get is never define a binary rule for a flat,
orderless function! Actually, that statement is too strong, a better message
would be: never define a binary rule for a flat, orderless function if you
plan to use that function with more than several arguments.
Now, as to your particular question, the difference in timing appears to be
a bug. It appears to be related to the rule
Plus[k : _?NumericQ, b : fc[y_]] := fc[k + y]
You may want to post a description of what you are trying to accomplish with
your code to the newsgroup, as I am sure you will get many useful responses.
Carl Woll
Physics Dept
U of Washington
"Petr Kujan" <kujanp at fel.cvut.cz> wrote in message
news:b92ha1$li0$1 at smc.vnet.net...
> 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}
>
>
> Thank you,
> Petr Kujan
> --
> kujanp at fel.cvut.cz
>
>