```Date: Apr 11, 2013 4:10 AM
Author: Albert Retey
Subject: Re: Timing puzzle

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 theirname - 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
```