Re: Why overloaded arithmetic operations are so slow?
- To: mathgroup at smc.vnet.net
- Subject: [mg49914] Re: [mg49729] Why overloaded arithmetic operations are so slow?
- From: "Fred Simons" <f.h.simons at tue.nl>
- Date: Fri, 6 Aug 2004 03:09:29 -0400 (EDT)
- References: <200407291145.HAA10328@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Sergey,
To explain what is going on I define a function that will produce a list of
zz-numbers:
In[1]:=
p[n_] := zz /@ Table[Random[Integer, {1,1000}], {n}]
and adapt the assignment to zz to visualize the evaluation process:
In[2]:=
Clear[zz];
zz/:Plus[z1_zz,z2_zz]:=(Print[{z1, z2}];zz[First[z1]+First[z2]])
The function Plus has attributes OneIdentity and Flat and these will be used
before the rule for zz is applied. That means that the arguments of Plus
will be sorted. The definition for zz uses only two arguments, so the
attribute Flat will be used to 'rewrite' the expression in such a way that
the rule for zz can be applied. Here is a small example.
In[4]:=
p[4]
Plus @@%
Out[4]=
{zz[64],zz[579],zz[447],zz[43]}
From In[4]:=
{zz[43],zz[64]}
From In[4]:=
{zz[107],zz[447]}
From In[4]:=
{zz[554],zz[579]}
Out[5]=
zz[1133]
Indeed, the arguments are sorted, brackets are placed around the first two
arguments and the rule is applied, the arguments are sorted, brackets are
placed around the first two arguments and the rule is applied and so on. But
when we look at a larger example, we observe that the pattern matcher does
not simply place brackets around the first two arguments. It seems to
consider practically all possibilities before brackets are placed. In the
following example we observe that nearly all the time is used for the
transition from 15 to 14 arguments.
In[6]:=
p[15]
Plus @@%
Hence in this example the patternmatcher could be improved. But actually the
problem is due to a not quite adequate definition for zz. What you really
want to do is repeatedly combining two arguments of Plus leaving the others
untouched. That can be done in the following way:
In[8]:=
Clear[zz];
zz/:Plus[z1_zz,z2_zz, z3___]:=Plus[zz[First[z1]+First[z2]], z3]
In[10]:=
Total[p[254]] // Timing
Out[10]=
{0.032 Second,zz[126441]}
Or without the recursion:
In[11]:=
Clear[zz];
zz/:Plus[z1__zz]:=zz[Plus @@ First /@ {z1}]
In[13]:=
test=p[10000];
(Total[test]) // Timing
Out[14]=
{0.266 Second,zz[4990657]}
I hoppe this answers your question. But if this example really is your
problem, it can be done much easier and faster without the zz-rule:
In[15]:=
test = p[20000];
Total[test]// Timing
zz[Fold[#1+#2[[1]]&, 0, test]] // Timing
zz[Total[First/@test]] // Timing
Out[16]=
{2.75 Second,zz[9987173]}
Out[17]=
{0.047 Second,zz[9987173]}
Out[18]=
{0.015 Second,zz[9987173]}
Kind regards,
Fred Simons
Eindhoven University of Technology
----- Original Message -----
From: "Sergey Afonin" <serg at msu.ru>
To: mathgroup at smc.vnet.net
Subject: [mg49914] [mg49729] Why overloaded arithmetic operations are so slow?
> Hi all.
>
> In "The Mathematica Book" (2.5.10) one can read that overloading
> standard arithmetic operations, such as Plus, for user-defined data is
> "much more convenient" than defining specific functions. But how this
> can be done efficiently? I want to define type of the form zz[Number]
> with the addition
>
> zz /: Plus[z1_zz, z2_zz] := zz[First[z1] + First[z2]]
>
> In fact, zz are "normal" numbers. The following statement prints out
> the time spent for addition wrt the number of elements...
>
> Do[Print[Timing[Plus @@ Table[zz[10^(i - 1)], {i, n}]]], {n, 15}]
>
>
> {0. Second, zz[1]}
> {0. Second, zz[11]}
> {0. Second, zz[111]}
> {0. Second, zz[1111]}
> {0. Second, zz[11111]}
> {0. Second, zz[111111]}
> {0. Second, zz[1111111]}
> {0.02 Second, zz[11111111]}
> {0.03 Second, zz[111111111]}
> {0.12 Second, zz[1111111111]}
> {0.35 Second, zz[11111111111]}
> {1.07 Second, zz[111111111111]}
> {3.31 Second, zz[1111111111111]}
> {10.07 Second, zz[11111111111111]}
> {30.81 Second, zz[111111111111111]}
>
> Is it normal?
>
> Best regards,
> Sergey Afonin
>