Subject: [xsl] RE: Using divide-and-conquer recursion to create a cumulative sequence From: "Costello, Roger L." <costello@xxxxxxxxx> Date: Wed, 23 Dec 2009 13:32:21 -0500 |
Hi Folks, On 11 December 2009 I inquired on this list about how to create a recursive, divide-and-conquer XSLT transform that creates a cumulative sequence (see below for my original post). Dimitre Novatchev and Hermann Stamm-Wilbrandt responded with excellent solutions. Dimitre provided a solution that used XSLT 2.0 and Hermann provided a solution that used 1.0 plus EXSLT extensions. I was interested in an XSLT 1.0 solution without using extensions. After reflecting on Dimitre's and Hermann's solutions, I came up with the below solution. I believe that it has a time complexity of O(n log2n). If I err in my complexity calculation, please let me know. Here is the XSLT: <xsl:template name="cumulative"> <xsl:param name="numberList" /> <xsl:param name="sum" select="0" /> <xsl:choose> <xsl:when test="not($numberList)" /> <xsl:when test="count($numberList) = 1"> <xsl:value-of select="$numberList + $sum" /> <xsl:text> </xsl:text> </xsl:when> <xsl:otherwise> <xsl:variable name="mid" select="floor(count($numberList) div 2)"/> <xsl:call-template name="cumulative"> <xsl:with-param name="numberList" select="$numberList[position() <= $mid]"/> <xsl:with-param name="sum" select="$sum"/> </xsl:call-template> <xsl:call-template name="cumulative"> <xsl:with-param name="numberList" select="$numberList[position() > $mid]"/> <xsl:with-param name="sum" select="$sum + sum($numberList[position() <= $mid])"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> /Roger -----Original Message----- From: Costello, Roger L. Sent: Friday, December 11, 2009 4:39 PM 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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Using divide-and-conquer , Hermann Stamm-Wilbra | Thread | Re: [xsl] RE: Using divide-and-conq, Dimitre Novatchev |
Re: [xsl] Find the string and apply, Mukul Gandhi | Date | Re: [xsl] RE: Using divide-and-conq, Dimitre Novatchev |
Month |