Re: Timing puzzle
- To: mathgroup at smc.vnet.net
- Subject: [mg130451] Re: Timing puzzle
- From: Sseziwa Mukasa <mukasa at gmail.com>
- Date: Fri, 12 Apr 2013 02:15:45 -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: <20130410045307.C5A526B55@smc.vnet.net> <20130411081108.9A1A26B04@smc.vnet.net>
>> 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 at 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 at 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.
>>
>>
- References:
- Timing puzzle
- From: carlos%colorado.edu@gtempaccount.com
- Re: Timing puzzle
- From: Bob Hanlon <hanlonr357@gmail.com>
- Timing puzzle