# Re: Using divide-and-conquer recursion to create a cu

 Subject: Re: Using divide-and-conquer recursion to create a cumulative sequence From: Dimitre Novatchev Date: Sat, 12 Dec 2009 07:59:54 -0800
```The FXSL function

f:scanl(\$pFun, \$pQ0, \$pList)

where

\$pList                 is a sequence of item()

\$pFun                is a function (actually a node -- matched by
a template) that takes wo items of the type of the  \$pList items and
produces another item of the same type

\$pQ0                 is an "initial item" so that \$pFun(\$pQ0,
\$pList)   can be calculated, and if\$pList is empty, then the result
of f:scanl(...) is \$pQ0

does exactly this. Just call it like this:

Here is a complete example:

<xsl:stylesheet version="2.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:f="http://fxsl.sf.net/"
exclude-result-prefixes="f"
>
<xsl:import href="../f/func-scanlDVC.xsl"/>
<xsl:import href="../f/func-Operators.xsl"/>

<xsl:output omit-xml-declaration="yes" indent="yes"/>

<xsl:template match="/">
<xsl:for-each select="f:scanl(f:add(), 0, 1 to 100000)">
<xsl:value-of select="concat(.,',')"/>
</xsl:for-each>
</xsl:template>
</xsl:stylesheet>

This transformation produces the sequence of running totals of the
sequence of the numbers 1 to 100 000  (100 thousand numbers), and the
result is:

0,1,3,6,10,15,21,28,36,45,55,66,78,91,105,120,136, ...,
4999650006,4999750003,4999850001,4999950000,5000050000,

Not only this transformation doesn't crash due to any reason (stack
overflow was expected :) ), but its transformation time with Saxon
was only 601 milliseconds:

Saxon 9.1.0.7J from Saxonica
Java version 1.6.0_17
Stylesheet compilation time: 520 milliseconds
Processing file:/C:\CVS-DDN\fxsl-xslt2\data\numList.xml
Building tree for file:/C:\CVS-DDN\fxsl-xslt2\data\numList.xml
using class net.sf.saxon.tinytree.TinyBuilder
Tree built in 1 milliseconds
Tree size: 35 nodes, 20 characters, 0 attributes
Execution time: 601 milliseconds
Memory used: 342403488
NamePool contents: 97 entries in 91 chains. 9 prefixes, 10 URIs

To return to the original question: How to write a DVC transformation
when the calculations of the "right half" depend on the result of the
calculations of the "left half"?

The answer is simple: use the result of calculating the function over
the "left half" as argument to the calculation of the function over
the "right half".

In particular, below is a snippet from   ../f/func-scanlDVC.xsl (the
DVC implementation of f:scanl() imported by the above stylesheet.

As we can see, the result of calculating the function over the "left
half" is produced in the variable \$vResult1, whose last item is then
used as an argument in producing the result over the "right half":

<xsl:sequence select=
"(\$vResult1,
int:scanl(\$pFun,
\$vResult1[last()],
\$pList[position() > \$vHalf],
0)
)"
/>

Here is the complete snippet from the code of f:scanl():

<xsl:import href="func-apply.xsl"/>

<xsl:function name="f:scanl" as="item()*">
<xsl:param name="pFun" as="element()"/>
<xsl:param name="pQ0"/>
<xsl:param name="pList" as="item()*"/>

<xsl:sequence select="int:scanl(\$pFun, \$pQ0, \$pList, 1)"/>
</xsl:function>

<xsl:function name="int:scanl" as="item()*">
<xsl:param name="pFun" as="element()"/>
<xsl:param name="pQ0"/>
<xsl:param name="pList" as="item()*"/>
<xsl:param name="pStarting" as="xs:integer"/>

<xsl:variable name="vLength" select="count(\$pList)"/>

<xsl:choose>
<xsl:when test="\$vLength > 1">
<xsl:variable name="vHalf" select="\$vLength idiv 2"/>

<xsl:variable name="vResult1"
select="int:scanl(\$pFun,
\$pQ0,
\$pList[position() &lt;= \$vHalf],
\$pStarting
)"/>
<xsl:sequence select=
"(\$vResult1,
int:scanl(\$pFun,
\$vResult1[last()],
\$pList[position() > \$vHalf],
0)
)"
/>
</xsl:when>

<xsl:otherwise>
<xsl:if test="\$pStarting">
<xsl:sequence select="\$pQ0"/>
</xsl:if>

<xsl:if test="exists(\$pList)">
<xsl:sequence select="f:apply(\$pFun, \$pQ0, \$pList)"/>
</xsl:if>
</xsl:otherwise>
</xsl:choose>
</xsl:function>

--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
I enjoy the massacre of ads. This sentence will slaughter ads without
a messy bloodbath.

On Fri, Dec 11, 2009 at 1:39 PM, Costello, Roger L. <costello@xxxxxxxxx>
wrote:
>
> Hi Folks,
>
> I wish to convert a sequence of N numbers:
>
> B  (23, 41, 70, 103, 99, 6)
>
> Into a cumulative sequence, in which each number is the sum of the previous
numbers:
>
> B  (23, 64, 134, 237, 336, 342)
>
>
> One approach to solving this is to iterate through the N numbers and sum the
preceding numbers:
>
> B  for i=1 to N
> B  B  B  sum(for j=1 to i return numbers[j])
>
>
> However, that approach has a time complexity of:
>
> B  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

```

### PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!