Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #14123 > unrolled thread

Timing puzzle

Started bycarlos%colorado.edu@gtempaccount.com
First post2013-04-10 04:48 +0000
Last post2013-04-13 06:02 +0000
Articles 4 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  Timing puzzle carlos%colorado.edu@gtempaccount.com - 2013-04-10 04:48 +0000
    Re: Timing puzzle awnl <awnl@gmx-topmail.de> - 2013-04-11 08:10 +0000
    Re: Timing puzzle carlos%colorado.edu@gtempaccount.com - 2013-04-12 06:16 +0000
      Re: Timing puzzle Daniel Lichtblau <danl@wolfram.com> - 2013-04-13 06:02 +0000

#14123 — Timing puzzle

Fromcarlos%colorado.edu@gtempaccount.com
Date2013-04-10 04:48 +0000
SubjectTiming puzzle
Message-ID<kk2qvl$bip$1@smc.vnet.net>
I am writing a graphics package that often creates objects with thousands of polygons, possibly up to 10^5. Out of curiosity I tested 5 ways of dynamically creating a plot list, using AppendTo, Append, Join, etc., and did the following timing test of 5 ways to do it:

ClearAll[poly,p,n]; poly={}; n00;
p[arg_]:= {mygraphic[mycolor[Random[],Random[],Random[]]],
                mygraphic[mypoly[{{Random[],Random[]},
                 {Random[],Random[]},{Random[],Random[]}}]]};
Print[Timing[Do[AppendTo[poly,p[i]],{i,1,n}]][[1]]]; 
ClearAll[poly]; poly={};
Print[Timing[Do[poly=Append[poly,p[i]],{i,1,n}]][[1]]];  
ClearAll[poly]; poly={};
Print[Timing[Do[poly=Join[poly,{p[i]}],{i,1,n}]][[1]]];
ClearAll[poly]; poly={};
Print[Timing[Do[poly={poly,{p[i]}},{i,1,n}];poly=Flatten[poly]][[1]]];
ClearAll[poly]; poly=Table[0,{n}];
Print[Timing[Do[poly[[i]]=p[i],{i,1,n}]][[1]]];

Running with n00 on a MacPro under Mac OSX 10.6.8 gives these times:

0.911327 Second
0.891656 Second
0.927267 Second
0.504454 Second
0.009575 Second

Question: why is the last method much faster?  I thought that appending an object to a list should take about the same time as storing an array entry.  When I worked with linked lists several decades ago (using assembly code on a CDC 7600) all I had to do is retrieve the object address,  manipulate registers, store in a pointer array, and presto! it was done.

[toc] | [next] | [standalone]


#14150

Fromawnl <awnl@gmx-topmail.de>
Date2013-04-11 08:10 +0000
Message-ID<kk5r5l$rhm$1@smc.vnet.net>
In reply to#14123
Hi,

> I am writing a graphics package that often creates objects with
> thousands of polygons, possibly up to 10^5. Out of curiosity I
> tested 5 ways of dynamically creating a plot list, using AppendTo,
> Append, Join, etc., and did the following timing test of 5 ways to do
> it:
>
> ClearAll[poly,p,n]; poly={}; n00; p[arg_]:=
> {mygraphic[mycolor[Random[],Random[],Random[]]],
> mygraphic[mypoly[{{Random[],Random[]},
> {Random[],Random[]},{Random[],Random[]}}]]};
> Print[Timing[Do[AppendTo[poly,p[i]],{i,1,n}]][[1]]]; ClearAll[poly];
> poly={}; Print[Timing[Do[poly=Append[poly,p[i]],{i,1,n}]][[1]]];
> ClearAll[poly]; poly={};
> Print[Timing[Do[poly=Join[poly,{p[i]}],{i,1,n}]][[1]]];
> ClearAll[poly]; poly={};
> Print[Timing[Do[poly={poly,{p[i]}},{i,1,n}];poly=Flatten[poly]][[1]]];
>
>
>
ClearAll[poly]; poly=Table[0,{n}];
> Print[Timing[Do[poly[[i]]=p[i],{i,1,n}]][[1]]];
>
> Running with n00 on a MacPro under Mac OSX 10.6.8 gives these times:
>
> 0.911327 Second 0.891656 Second 0.927267 Second 0.504454 Second
> 0.009575 Second
>
> Question: why is the last method much faster?  I thought that
> appending an object to a list should take about the same time as
> storing an array entry.  When I worked with linked lists several
> decades ago (using assembly code on a CDC 7600) all I had to do is
> retrieve the object address,  manipulate registers, store in a
> pointer array, and presto! it was done.

the answer is pretty obvious: Lists in Mathematica are - despite their
name - not linked lists but arrays. It can be argued whether that was a 
good decision or not, but you certainly have to live with that fact and 
remember it if efficiency matters...

You should check your results of case 4, this is a well known 
"Mathematica emulation" of linked lists and should be much faster: on my 
computer (Windows 7, Mathematica 9) with n=10000 it is just as fast as the Do 
loop which sets the preallocated table entries...

hth,

albert

[toc] | [prev] | [next] | [standalone]


#14157

Fromcarlos%colorado.edu@gtempaccount.com
Date2013-04-12 06:16 +0000
Message-ID<kk88rk$c1g$1@smc.vnet.net>
In reply to#14123
Clarification: n was 1000 in the posted test; for some reason the top line was mangled in copy/paste.
For n=5000 the results are

5.37185 Second
5.27741 Second
5.41862 Second
3.18303 Second
0.024265 Second

Conclusion: time for the top 4 goes up ~linearly, which suggests that the list is being modified by just appending one item, instead of placing a pointer to it.  For the last one it goes up sublinearly.

Reason for worry: in the actual plot package n is not known until the plot is finished. My  plotter actually builds dynamically three Graphics3D sublists: faces, edges, points and labels. Optional commands such as changing point size, thickness, colors and font styles, may be inserted at any point in those sublists.  So the faster method (preallocating addresses with Table) is ruled out.


[toc] | [prev] | [next] | [standalone]


#14173

FromDaniel Lichtblau <danl@wolfram.com>
Date2013-04-13 06:02 +0000
Message-ID<kkasdn$rj9$1@smc.vnet.net>
In reply to#14157
On Apr 12, 1:16 am, carlos%colorado....@gtempaccount.com wrote:
> Clarification: n was 1000 in the posted test; for some reason the top line was mangled in copy/paste.
> For n=5000 the results are
>
> 5.37185 Second
> 5.27741 Second
> 5.41862 Second
> 3.18303 Second
> 0.024265 Second
>
> Conclusion: time for the top 4 goes up ~linearly, which suggests that the list is being modified by just appending one item, instead of placing a pointer to it.  For the last one it goes up sublinearly.
>
> Reason for worry: in the actual plot package n is not known until the plot is finished. My  plotter actually builds dynamically three Graphics3D sublists: faces, edges, points and labels. Optional commands such as changing point size, thickness, colors and font styles, may be inserted at any point in those sublists.  So the faster method (preallocating addresses with Table) is ruled out.

Method 4 in any recent version (8 or 9 or even 7 with a nondefault
system option setting) should be fine for this. Use of Sow and Reap,
likewise, and with every version since I gorget which, but probably 4.

As others have noted, a Mathematica list is akin to what is often
called an array in computer science. It is not a linked list under the
hood, and will not behave like one in terms of computational
complexity. Actually this forum has seen related discussion going well
back into the last millenium.

If you desperately want to emulate a linked list, one way to do so is
described at

http://stackoverflow.com/questions/6691491/implementing-a-quadtree-in-mathematica/6795762#6795762

Title notwithstanding, there is a bit about linked lists near the end.

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web