Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Software » comp.soft-sys.math.mathematica

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Sseziwa Mukasa

Posts: 108
Registered: 8/26/07
Re: Timing puzzle
Posted: Apr 12, 2013 2:15 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

>> 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
Read Re: Timing puzzle
Bob Hanlon
4/12/13
Read Re: Timing puzzle
Sseziwa Mukasa

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.