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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

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[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"
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
   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=
         "($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[1])"/>
        </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