[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Cheaper to prepend or append an item to a sequence

Subject: Re: Cheaper to prepend or append an item to a sequence?
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Tue, 22 Feb 2011 06:40:43 -0800
Re:  Cheaper to prepend or append an item to a sequence
> Even with a forward-chained list, you can implement append without copying
> if you choose, at least for the first append operation to a given list
> (which 9 times out of 10 will be the only append operation).

What people want is to be able to append one list to another in O(N)
time, not in O(N^2).

This is why people chose to pre-pend the elements of the second list
(starting from the last) to the first list.


Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.



On Tue, Feb 22, 2011 at 6:32 AM, Michael Kay <mike@xxxxxxxxxxxx> wrote:
> On 22/02/2011 13:58, Dimitre Novatchev wrote:
>>
>> The accepted term in most functional programming languages is "a list".
>>
>> A list is a functional data structure (immutable). Appending to a list
>> causes the whole list to be copied and is O(N). Prepending a list is
>> making just the "next pointer" of an item point to the list -- an O(1)
>> operation.
>>
>
> Even with a forward-chained list, you can implement append without copying
> if you choose, at least for the first append operation to a given list
> (which 9 times out of 10 will be the only append operation).
>
> Michael Kay
> Saxonica
>
>



--

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.