Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2013

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

Search the Archive

Re: Timing puzzle

  • To: mathgroup at smc.vnet.net
  • Subject: [mg130437] Re: Timing puzzle
  • From: awnl <awnl at gmx-topmail.de>
  • Date: Thu, 11 Apr 2013 04:11:28 -0400 (EDT)
  • Delivered-to: l-mathgroup@mail-archive0.wolfram.com
  • Delivered-to: l-mathgroup@wolfram.com
  • Delivered-to: mathgroup-newout@smc.vnet.net
  • Delivered-to: mathgroup-newsend@smc.vnet.net
  • References: <kk2qvl$bip$1@smc.vnet.net>

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




  • Prev by Date: Re: Timing puzzle
  • Next by Date: Re: Sample Workbooks - Suggested sources to get a newbie going?
  • Previous by thread: Re: Timing puzzle
  • Next by thread: Re: Timing puzzle