Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Timing puzzle
Replies: 3   Last Post: Apr 12, 2013 2:15 AM

 Messages: [ Previous | Next ]
 Sseziwa Mukasa Posts: 108 Registered: 8/26/07
Re: Timing puzzle
Posted: Apr 12, 2013 2:15 AM

>> 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.

Retrieving an object address usually requires memory allocation which is an expensive operation. Moreover, since Mathematica expressions don't modify their arguments in general, every time a result is generated memory has to be allocated for it. So AppendTo and Append, have to allocate a list one element larger than the first argument then copy the contents of the two arguments. Table, Map etc. can determine the size of the result once from the iterator bounds or length of the argument, allocate the memory once, then copy the results as necessary. So the Append based routines will do O(n^2) memory allocations compared to O(1) for Table and Map and that's the primary source of the timing difference.

This is why the help note on Append points out that it's an inefficient way to build a list iteratively:

In iteratively building a list, it is usually more efficient to use Sow and Reap than to use Append[list,new] at each step.

Regards,
Sseziwa

On Apr 11, 2013, at 4:11 AM, Bob Hanlon <hanlonr357@gmail.com> wrote:

>
> I've added a couple of additional (faster) methods. You did not indicate
> the value of n that you used. These timings are with Mathematica v9.0.1.0
> on a MacBook Air (2.13 GHz Intel Core 2 Duo; OS X 10.8.3) and n = 10^4.
>
> poly initialization (when required) moved inside Timing to level the
> playing field.
>
> Removed unnecessary Print statements.
>
>
> ClearAll[p];
> n = 10^4;
>
>
> p[arg_] := {
> mygraphic[
> mycolor[Random[], Random[], Random[]]],
> mygraphic[
> mypoly[{
> {Random[], Random[]},
> {Random[], Random[]},
> {Random[], Random[]}}]]};
>
> Timing[poly = {}; Do[
> AppendTo[poly, p[i]], {i, n}]][[1]]
>
> Timing[poly = {}; Do[
> poly = Append[poly, p[i]], {i, n}]][[1]]
>
> Timing[poly = {}; Do[
> poly = Join[poly, {p[i]}], {i, n}]][[1]]
>
> Timing[poly = {}; Do[
> poly = {poly, {p[i]}}, {i, n}];
> poly = Flatten[poly]][[1]]
>
> Timing[poly = Table[0, {n}];
> Do[poly[[i]] = p[i], {i, n}]][[1]]
>
> Timing[
> poly = Table[p[i], {i, n}]][[1]]
>
> Timing[
> poly = p /@ Range[n]][[1]]
>
>
> 4.510119
> 4.384446
> 4.646620
> 0.106249
> 0.089704
> 0.079244
> 0.072297
>
>
>
> Bob Hanlon
>
>
> On Wed, Apr 10, 2013 at 12:53 AM, <carlos%colorado.edu@gtempaccount.com>wrote:
>

>> 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.
>>
>>

Date Subject Author
4/11/13 Bob Hanlon
4/12/13 Sseziwa Mukasa