xsl-list
[Top] [All Lists]

Re: [xsl] Cheaper to prepend or append an item to a sequence?

2011-02-22 07:59:29
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.

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:

http://dnovatchev.wordpress.com/2008/12/22/performance-feat-eliminate-a-dimension-of-complexity-in-xslt-processors-repetitive-prepends-part-ii-the-solution/



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 3:27 AM, Costello, Roger L. 
<costello(_at_)mitre(_dot_)org> wrote:
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

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: 
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--





--

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

<Prev in Thread] Current Thread [Next in Thread>