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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

> Dimitre provided a solution that used XSLT 2.0 and Hermann provided a
solution that used 1.0 plus EXSLT extensions.


I did so, because I believe nobody (almost) USES xslt 1.0 nowadays.

Exactly the same solution ( using <xsl:choose> and not XPath 2.0) is
part of the FXSL 1.x (for XSLT 1.0).


--
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 Wed, Dec 23, 2009 at 10:32 AM, Costello, Roger L. <costello@xxxxxxxxx>
wrote:
>
> Hi Folks,
>
> On 11 December 2009 I inquired on this list about how to create a recursive,
divide-and-conquer XSLT transform that creates a cumulative sequence (see
below for my original post).
>
> Dimitre Novatchev and Hermann Stamm-Wilbrandt responded with excellent
solutions. Dimitre provided a solution that used XSLT 2.0 and Hermann provided
a solution that used 1.0 plus EXSLT extensions.
>
> I was interested in an XSLT 1.0 solution without using extensions. After
reflecting on Dimitre's and Hermann's solutions, I came up with the below
solution. I believe that it has a time complexity of O(n log2n). If I err in
my complexity calculation, please let me know.
>
> Here is the XSLT:
>
> B  B <xsl:template name="cumulative">
> B  B  B  B <xsl:param name="numberList" />
> B  B  B  B <xsl:param name="sum" select="0" />
>
> B  B  B  B <xsl:choose>
> B  B  B  B  B  B <xsl:when test="not($numberList)" />
> B  B  B  B  B  B <xsl:when test="count($numberList) = 1">
> B  B  B  B  B  B  B  B <xsl:value-of select="$numberList + $sum" />
> B  B  B  B  B  B  B  B <xsl:text> </xsl:text>
> B  B  B  B  B  B </xsl:when>
> B  B  B  B  B  B <xsl:otherwise>
> B  B  B  B  B  B  B  B <xsl:variable name="mid"
select="floor(count($numberList) div 2)"/>
> B  B  B  B  B  B  B  B <xsl:call-template name="cumulative">
> B  B  B  B  B  B  B  B  B  B <xsl:with-param name="numberList"
select="$numberList[position() &lt;= $mid]"/>
> B  B  B  B  B  B  B  B  B  B <xsl:with-param name="sum" select="$sum"/>
> B  B  B  B  B  B  B  B </xsl:call-template>
> B  B  B  B  B  B  B  B <xsl:call-template name="cumulative">
> B  B  B  B  B  B  B  B  B  B <xsl:with-param name="numberList"
select="$numberList[position() &gt; $mid]"/>
> B  B  B  B  B  B  B  B  B  B <xsl:with-param name="sum" select="$sum +
sum($numberList[position() &lt;= $mid])"/>
> B  B  B  B  B  B  B  B </xsl:call-template>
> B  B  B  B  B  B </xsl:otherwise>
> B  B  B  B </xsl:choose>
> B  B </xsl:template>
>
> /Roger
>
> -----Original Message-----
> From: Costello, Roger L.
> Sent: Friday, December 11, 2009 4:39 PM
> To: 'xsl-list@xxxxxxxxxxxxxxxxxxxxxx'
> Subject: Using divide-and-conquer recursion to create a cumulative sequence
>
> 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
>



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