Re: efficiency of Mma list operations
- To: mathgroup at yoda.physics.unc.edu
- Subject: Re: efficiency of Mma list operations
- From: gaylord at ux1.cso.uiuc.edu
- Date: Tue, 5 May 1992 08:00:51 -0500
David Jacobson writes:
constestf[n_] :=
Block[{foo=Cons[]},Do[foo=Cons[foo,a],{n}];
Apply[List,Flatten[foo,Infinity,Cons]]]
In[24]:= Table[{10^n,First[Timing[constestf[10^n]]]},{n,2,5}]
Out[24]= {{100, 0.01 Second}, {1000, 0.1 Second}, {10000, 1.04 Second},
{100000, 10.49 Second}}
So you can see that up to 100000 items the time for appending an item using
Cons was apparently constant.
=========================================
comparing this to the use of Table for list construction
constestf[n_] :=
Block[{foo=Cons[]},Do[foo=Cons[foo,a],{n}];
Apply[List,Flatten[foo,Infinity,Cons]]]
constestf[10]
{a, a, a, a, a, a, a, a, a, a}
{Timing[constestf[100];],Timing[Table[a, {100}];]}
{{0.283333 Second, Null}, {0. Second, Null}}
{Timing[constestf[1000];],Timing[Table[a, {1000}];]}
{{0.75 Second, Null}, {0.0666667 Second, Null}}
{Timing[constestf[10000];],Timing[Table[a, {10000}];]}
{{7.25 Second, Null}, {0.6 Second, Null}}
{Timing[constestf[100000];],Timing[Table[a, {100000}];]}
-dialogue box saying Mathematica unexpectedly quit due to an error of type
-28-
------------------------------
we can conclude that
(1) David's machine runs about 7 times faster than my Mac IIfx (david-what
are you using?) and does not have memory problem with Mathematica (I have
Mathematica set for 15 Mb).
(2) The trend of timing vs. length is the same for both constestf and Table
(although Table is 10 times faster for a given length [thus supporting the
view that one try to should use built-in functions whenever possible]
(3) in constructing the list of {..a,a,a...}, Mathematica is not evaluating
each element (this can also be demonstrated using a suitable expr in
Table[expr,{n}])
(we know that M is not an infinite evaluation system but follows certain
heuristics in doing evaluation).
(4) finally, Table should be kept in mind as a tool for list construction.