Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2006
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Efficiency of repeatedly appending to a List


On my computer, the graph comes out like a lie detector test on
someone who is working out.

On 11/9/06, Sseziwa Mukasa <mukasa at jeol.com> wrote:
>
> On Nov 8, 2006, at 6:14 AM, Andrew Moylan wrote:
>
> > Hi all,
> >
> > Recently I asked about efficient ways to insert items into a sorted
> > List such that the new list was also sorted [1]. I received
> > suggestions
> > to linearly search through the list and find the right place to insert
> > the new time (search time = O(N), where N is the size of the list),
> > and
> > also suggestions to use a faster binary search to locate the right
> > place to insert the new time (search time = O(Log[N])).
>
> I'm one of those who naively suggested an O(N) search, and I should
> know better.  Also I somehow had never heard of the Insert command,
> the two together are probably more efficient than Appending then
> sorting since the sort should be O(N Log[N]).  I had also never
> bothered to check whether a binary search would be in the
> Combinatorica package, which it is.  So here's the code for a binary
> search and insertion:
>
> <<DiscreteMath`Combinatorica
> insertSorted[lst_,elem_]:=Insert[lst,elem,Ceiling[BinarySearch
> [lst,elem]]]
>
> > This caused me to wonder about the efficiency of appending items to
> > Lists in Mathematica in general. Is it an O(N) operation (i.e.,
> > something akin to a realloc in C)? Or does Mathematica employ some
> > sort
> > of anticipatory memory allocation scheme to make adding new
> > elements to
> > lists usually faster than O(N)?
>
> One way to test this is to Append to lists of various sizes and look
> for discontinuities and a general trend, because of restrictions on
> the mailing list I can't append a plot, but running this code plots
> the timing of Append to lists of various sizes.
>
> Block[{data,lst,x},data=Table[{len,lst=Table[x,{len}];First[Timing
> [Append[lst,x]]/.Second->1]},{len,1000,30000}];ListPlot
> [data,PlotRange->All,PlotJoined->True,AxesLabel->{"Length","Time
> (s)"}]];
>
> There is definitely an O(N) trend to the data, interestingly there is
> also an increasing variance in the data as the list size increases.
> There also seems to be a discontinuity right around a list length of
> 2000 when plotted on my machine (dual 2.7 GHz G5, Mac OS X).  The
> discontinuity seems to indicate that at least for short lists extra
> memory is allocated, but in general appending to a list is an O(N)
> operation.  Changing the type of x moves the discontinuity, setting
> x=1 moves the discontinuity to around 4000 elements and results in a
> much lower slope.  I suppose if one is really interested in this kind
> of investigation there is room for futher research but given the
> times involved (less than 0.5ms) I'm not sure how useful this
> knowledge would be.  Mathematica is not well suited to large scale
> data manipulation of this type in my experience and one should
> probably chose a different tool if the majority of operations are
> manipulation of large data structures in memory.
>
> Regards,
>
> Ssezi
>
>


-- 
http://chris.chiasson.name/


  • Prev by Date: Re: Easy way to 're-order' the axes in Plot3D
  • Next by Date: Re: [Help Needed] Converting C++ program into Mathematica Function
  • Previous by thread: Re: Efficiency of repeatedly appending to a List
  • Next by thread: Efficiency of repeatedly appending to a List