[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: RE: Using divide-and-conquer recursion to create a
> 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() <= $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() > $mid]"/> > B B B B B B B B B B <xsl:with-param name="sum" select="$sum + sum($numberList[position() <= $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.
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|