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: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Sat, 12 Dec 2009 07:59:54 -0800
The FXSL function

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


    $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[1])   can be calculated, and if$pList is empty, then the result
of f:scanl(...) is $pQ0

does exactly this. Just call it like this:

          f:scanl(f:add(), 0, $pList)

Here is a complete example:

<xsl:stylesheet version="2.0"
  <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(.,',')"/>

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

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 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
   Loading net.sf.saxon.event.MessageEmitter
   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=
                     $pList[position() > $vHalf],

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 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:when test="$vLength > 1">
        <xsl:variable name="vHalf" select="$vLength idiv 2"/>

        <xsl:variable name="vResult1"
                             $pList[position() &lt;= $vHalf],
        <xsl:sequence select=
                     $pList[position() > $vHalf],

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

        <xsl:if test="exists($pList)">
          <xsl:sequence select="f:apply($pFun, $pQ0, $pList[1])"/>

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

Current Thread