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

RE: Using divide-and-conquer recursion to create a cu

Subject: RE: Using divide-and-conquer recursion to create a cumulative sequence
From: "Michael Kay" <mike@xxxxxxxxxxxx>
Date: Fri, 11 Dec 2009 22:08:18 -0000
RE:  Using divide-and-conquer recursion to create a  cu
Actually, as I point out in the book, you need to be fairly careful how you
code this if you want to take advantage of tail recursion even in a
processor that offers this optimization. (I don't offer the solution in the
book and I'm not offering it here - there are other things I want to get
done this evening!)

I don't think the classic divide-and-conquer works here, because you can't
process the right-hand half of the sequence independently of the left-hand
half. There may be ways of breaking up the problem, but nothing comes to

XSLT 2.1 will offer a new construct for this kind of problem. xsl:iterate is
like an xsl:for-each except that each iteration can set parameters to be
used in the next iteration. The final result is delivered by the
xsl:on-completion instruction. Here's the sample code:

<xsl:iterate select="input">
  <xsl:param name="total-so-far" select="0"/>
  <xsl:variable name="next-total" select="$total-so-far + ."/>
    <xsl:with-param name="total-so-far" select="$next-total"/>
  <xsl:on-completion select="$next-total"/>

The primary motivation was that it's easier to compile this for processing
streamed input than the same operation written recursively; but it's also
easier, I think, for people to get their mind around than head-tail
recursion, and it's also less demanding on the optimizer. There's a preview
of the construct (implemented as extensions in the Saxon namespace) in Saxon


Michael Kay


> -----Original Message-----
> From: Costello, Roger L. [mailto:costello@xxxxxxxxx] 
> Sent: 11 December 2009 21:39
> To: 'xsl-list@xxxxxxxxxxxxxxxxxxxxxx'
> Subject:  Using divide-and-conquer recursion to create a 
> cumulative sequence
> Hi Folks,
> I wish to convert a sequence of N numbers:
>    (23, 41, 70, 103, 99, 6)
> Into a cumulative sequence, in which each number is the sum 
> of the previous numbers:
>    (23, 64, 134, 237, 336, 342)
> One approach to solving this is to iterate through the N 
> numbers and sum the preceding numbers:
>    for i=1 to N
>        sum(for j=1 to i return numbers[j])
> However, that approach has a time complexity of:
>    1 + 2 + 3 + ... + N = N**2/2
> For large N, that will be very expensive.
> An alternative approach is to create a recursive function 
> that does a single pass through the sequence, carrying along 
> (and adding) the accumulated total on each recursive call. 
> This has a time complexity of N. Nice.
> *********************************************************************
> The above (paraphrases) from Michael Kay's book, XSLT 2.0 and 
> XPath 2.0, p. 993.
> The below is from me.
> *********************************************************************
> However, that sequential recursive approach will entail N 
> recursive calls, which will result in running out of memory 
> for large N (let's assume that the XSLT processor does not do 
> tail recursive optimization).
> I would like a way of solving the problem using 
> divide-and-conquer recursion. Can you provide a solution? 
> /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.