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

[Hermann Stamm-Wilbrandt <STAMMW@xxxxxxxxxx>]

Hi,

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
elements.
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  = "http://www.w3.org/1999/XSL/Transform";
  xmlns:exsl = "http://exslt.org/common";
  xmlns:str  = "http://exslt.org/strings";
  xmlns:func = "http://exslt.org/functions";
  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))"/>
    <seq>
      <xsl:value-of select="$res/*[1]"/>
      <xsl:for-each select="$res/*[position() &gt; 1]"
        >, <xsl:value-of select="."/></xsl:for-each>
    </seq>
  </xsl:template>

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

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

        <func:result>
          <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])"/>
        </func:result>
      </xsl:otherwise>
    </xsl:choose>
  </func:function>

</xsl:stylesheet>
$

http://stamm-wilbrandt.de/en/xsl-list/seq.xsl


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





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