xsl-list
[Top] [All Lists]

[xsl] RE: Using divide-and-conquer recursion to create a cumulative sequence

2009-12-23 13:32:52
 
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() &lt;= $mid]"/>
                    <xsl:with-param name="sum" select="$sum"/>
                </xsl:call-template>
                <xsl:call-template name="cumulative">
                    <xsl:with-param name="numberList" 
select="$numberList[position() &gt; $mid]"/>
                    <xsl:with-param name="sum" select="$sum + 
sum($numberList[position() &lt;= $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(_at_)lists(_dot_)mulberrytech(_dot_)com'
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
--~------------------------------------------------------------------
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>
--~--