On Sat, 2004-03-27 at 14:46, Majorinc, Kazimir wrote: > Dear colleagues, > > Icon (and Unicon) advantages over lists implemented through pointers, i.e. > direct access using integers as indexes seems to have a price: some tests I > did recently suggest that linear time is required for the insertion (and > perhaps deletition) of elements with known index from list (using built in > functions or list concatenation). Am I right about that?
Majorinc, Insertion (adding a new element, thus increasing the size of the list) is expensive, but the cost is not uniform across all insertions. Lists 'grow' internally by a fixed size block. Way back this internal block could hold upto 8 elements - I don't know if this number is still true. So adding an element might be cheap (there's room in the current block) or expensive (a new block is needed). However, this *only* applies to 'inserting' at the ends of the list - there is no operation that inserts elements anywhere else in a list (as you know). So, yes, arbitrary element insertion is expensive because you have to construct a brand new list from the new element and pieces of the old list. Arbitrary deletion is similarly expensive. (Deletion from an end of the list is cheap, however!) Using a table with integer keys might be faster if you want to mimic a list with arbitrary insertions and deletions (though really deleting an element from a table is problematic). I don't understand your comment about having both table indexing and insertion in the same time but not both at the same time, could you expand on that? > Is there a convenient way around, or a new data structure that allows > direct access (with enumerable i.e. integer indexes) in const or log time > and fast (const or log time) insertion is required? (Using tables it > appears one can have both integer indexes and insertion in a linear time, > but not both in the same time) I guess that some kind of a balanced tree > (perhaps table with some extensions) can do that. Did anyone implemented > such a data structure or operations already? -- Steve Wampler <[EMAIL PROTECTED]> ------------------------------------------------------- This SF.Net email is sponsored by: IBM Linux Tutorials Free Linux tutorial presented by Daniel Robbins, President and CEO of GenToo technologies. Learn everything from fundamentals to system administration.http://ads.osdn.com/?ad_id=1470&alloc_id=3638&op=click _______________________________________________ Unicon-group mailing list [EMAIL PROTECTED] https://lists.sourceforge.net/lists/listinfo/unicon-group
