[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 05:58:55 -0800
Re:  Cheaper to prepend or append an item to a sequence
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)

To summarize, in most functional languages prepending is O(1) and
appending is O(N).

However, everything depends on the implementation. Sometimes the
implementors choose some unorthodox internal structure in which
appending is the cheaper operation and prepending is the much slower
operation -- I think Saxon behaves (behaved AFAIR) in this way.

There are algorithms how to optimize continuous appending (or
pre-pending in the unorthodox case) to be O(N) and not O(N^2). I even
showed how to do fast multiple prepending to a Saxon sequence -- see
this post in my blog:


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 3:27 AM, Costello, Roger L. <costello@xxxxxxxxx>
> Hi Folks,
> When adding an item to a sequence, it is: (circle the correct answer)
> (a) Cheaper to add the item to the front of the sequence
> (b) Cheaper to add the item to the end of the sequence
> (c) Costs the same to add the item to the front or to the end
> (d) The cost varies depending on the XSLT processor
> /Roger


Current Thread


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.
First Name
Last Name
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.