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() > 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() <= $mid]))"/>
<xsl:copy-of select="$lftres"/>
<xsl:copy-of select=
"my:seqSum($lftres/*[last()], $seq[position() > $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(_at_)mitre(_dot_)o
To
rg>
"'xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com'"
<xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com>
12/11/2009 10:39 cc
PM
Subject
[xsl] Using divide-and-conquer
Please respond to recursion to create a cumulative
xsl-list(_at_)lists(_dot_)mu 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
--~------------------------------------------------------------------
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>
--~--
--~------------------------------------------------------------------
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>
--~--