[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
RE: [xsl] Using divide-and-conquer recursion to create a cumulative sequence
Subject: RE: [xsl] Using divide-and-conquer recursion to create a cumulative sequence From: "Michael Kay" <mike@xxxxxxxxxxxx> Date: Fri, 11 Dec 2009 22:08:18 -0000 |
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 mind. 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:next-iteration> <xsl:with-param name="total-so-far" select="$next-total"/> </xsl:next-iteration> <xsl:on-completion select="$next-total"/> </xsl:iterate> 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 9.2. Regards, Michael Kay http://www.saxonica.com/ http://twitter.com/michaelhkay > -----Original Message----- > From: Costello, Roger L. [mailto:costello@xxxxxxxxx] > Sent: 11 December 2009 21:39 > To: 'xsl-list@xxxxxxxxxxxxxxxxxxxxxx' > Subject: [xsl] 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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Using divide-and-conquer recu, Costello, Roger L. | Thread | RE: [xsl] Using divide-and-conquer , Michael Kay |
[xsl] Using divide-and-conquer recu, Costello, Roger L. | Date | RE: [xsl] Using divide-and-conquer , Michael Kay |
Month |