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: Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>
Date: Sun, 13 Dec 2009 21:26:15 +0100

just saw that others already responded with different solutions.
This is a XSLT 1.0 solution (with EXSLT extensions).

xsltproc does not support func:funtion, therefore the use of xalan-j_2_7_1.
tail-recursive solution runs into stack overflow for sequences of 350
Below soution is able to deal with sequences up to 13000 elements.

$ cat seq.xml
<seq>23, 41, 70, 103, 99, 6</seq>
$ java -jar xalan.jar -XSL seq.xsl -IN seq.xml ; echo
<?xml version="1.0" encoding="UTF-8"?><seq>23, 64, 134, 237, 336, 342</seq>
$ cat seq.xsl
<xsl:stylesheet version="1.0"
  xmlns:xsl  = "";
  xmlns:exsl = "";
  xmlns:str  = "";
  xmlns:func = "";
  xmlns:my   = "urn:my"
  exclude-result-prefixes="exsl str func my"

  <xsl:template match="/">
    <xsl:variable name="seq" select="str:tokenize(., ',')"/>

    <xsl:variable name="res" select="exsl:node-set(my:seqSum(0, $seq))"/>
      <xsl:value-of select="$res/*[1]"/>
      <xsl:for-each select="$res/*[position() &gt; 1]"
        >, <xsl:value-of select="."/></xsl:for-each>

  <func:function name="my:seqSum">
    <xsl:param name="sum"/>
    <xsl:param name="seq"/>

      <xsl:when test="count($seq) = 1">
          <a><xsl:copy-of select="$sum + $seq[1]"/></a>
        <xsl:variable name="mid" select="floor(count($seq) div 2)"/>

          <xsl:variable name="lftres" select=
            "exsl:node-set(my:seqSum($sum, $seq[position() &lt;= $mid]))"/>
          <xsl:copy-of select="$lftres"/>
          <xsl:copy-of select=
            "my:seqSum($lftres/*[last()], $seq[position() &gt; $mid])"/>


Mit besten Gruessen / Best wishes,

Hermann Stamm-Wilbrandt
Developer, XML Compiler
WebSphere DataPower SOA Appliances
IBM Deutschland Research & Development GmbH
Vorsitzender des Aufsichtsrats: Martin Jetter
Geschaeftsfuehrung: Dirk Wittkopp
Sitz der Gesellschaft: Boeblingen
Registergericht: Amtsgericht Stuttgart, HRB 243294

             "Costello, Roger                                              
             <costello@xxxxxxx                                          To 
             rg>                       "'xsl-list@xxxxxxxxxxxxxxxxxxxxxx'" 
             12/11/2009 10:39                                           cc 
                                       [xsl] Using divide-and-conquer      
             Please respond to         recursion to create a cumulative    
             xsl-list@xxxxxxxx         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

   (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.

The above (paraphrases) from Michael Kay's book, XSLT 2.0 and XPath 2.0, p.
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?


Current Thread