[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

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 <dnovatchev@xxxxxxxxx>
Date: Sat, 12 Dec 2009 07:59:54 -0800
Re:  Using divide-and-conquer recursion to create a  cu
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

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

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

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.