Subject: RE: [xsl] Using divideandconquer 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 divideandconquer works here, because you can't process the righthand half of the sequence independently of the lefthand 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:foreach except that each iteration can set parameters to be used in the next iteration. The final result is delivered by the xsl:oncompletion instruction. Here's the sample code: <xsl:iterate select="input"> <xsl:param name="totalsofar" select="0"/> <xsl:variable name="nexttotal" select="$totalsofar + ."/> <xsl:nextiteration> <xsl:withparam name="totalsofar" select="$nexttotal"/> </xsl:nextiteration> <xsl:oncompletion select="$nexttotal"/> </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 headtail 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: 'xsllist@xxxxxxxxxxxxxxxxxxxxxx' > Subject: [xsl] Using divideandconquer 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 > divideandconquer recursion. Can you provide a solution? > > /Roger
Current Thread 


< Previous  Index  Next > 

[xsl] Using divideandconquer recu, Costello, Roger L.  Thread  RE: [xsl] Using divideandconquer , Michael Kay 
[xsl] Using divideandconquer recu, Costello, Roger L.  Date  RE: [xsl] Using divideandconquer , Michael Kay 
Month 