Re: Re: Efficiency of repeatedly appending to a List
- To: mathgroup at smc.vnet.net
- Subject: [mg71185] Re: [mg71148] Re: [mg71091] Efficiency of repeatedly appending to a List
- From: "Chris Chiasson" <chris at chiasson.name>
- Date: Fri, 10 Nov 2006 06:37:39 -0500 (EST)
- References: <200611081114.GAA22363@smc.vnet.net> <200611090838.DAA15675@smc.vnet.net>
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/
- References:
- Efficiency of repeatedly appending to a List
- From: "Andrew Moylan" <andrew.j.moylan@gmail.com>
- Re: Efficiency of repeatedly appending to a List
- From: Sseziwa Mukasa <mukasa@jeol.com>
- Efficiency of repeatedly appending to a List