Re: Efficiency of repeatedly appending to a List
- To: mathgroup at smc.vnet.net
- Subject: [mg71149] Re: [mg71091] Efficiency of repeatedly appending to a List
- From: János <janos.lobb at yale.edu>
- Date: Thu, 9 Nov 2006 03:38:37 -0500 (EST)
- References: <200611081107.GAA21892@smc.vnet.net>
On Nov 8, 2006, at 6:07 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])). > > 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)? > > Cheers, > Andrew > > [1] > http://groups-beta.google.com/group/comp.soft-sys.math.mathematica/ > browse_thread/thread/0c329c83dec5a1b1 Appending to large lists are very expensive. I wish Mathemetica has had other constructs handy like LIFO, FIFO, and UFO :) János
- References:
- Efficiency of repeatedly appending to a List
- From: "Andrew Moylan" <andrew.j.moylan@gmail.com>
- Efficiency of repeatedly appending to a List