Subject: RE: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once? From: "Michael Kay" <michael.h.kay@xxxxxxxxxxxx> Date: Thu, 8 Nov 2001 14:27:08 -0000 |
The reason the tail-recursive version is taking longer is that each time round the loop, it makes a copy of the complete tree built so far. It's therefore not surprising that it has O(n^n) performance (not at all the same thing as increasing exponentially, by the way!). The non-tail-recursive solution creates a single temporary tree, adding nodes to it at each level of recursion, and never copying the tree until its final iteration. As for the divide-and-conquer algorithm, it looks interesting and performs well, but as it produces completely different output from the other two, I can't quite see the relevance. Mike Kay > -----Original Message----- > From: owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx > [mailto:owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx]On Behalf Of > Jeni Tennison > Sent: 07 November 2001 18:31 > To: Tom Myers > Cc: xsl-list@xxxxxxxxxxxxxxxxxxxxxx > Subject: Re: [xsl] Re: lookup-table thoughts (was Re: > matching multiple > times, outputting once? > > > Hi Tom, > > > However, I think making R tail-recursive is a success only if the > > "cons" is constant-time. > > The proof of the pudding is in the eating, as they say. It seems > you're right. I tried the following tail-recursive, non-tail-recursive > and divide-and-conquer templates with Saxon 6.4.4: > > <xsl:template name="embedTailRecursive"> > <xsl:param name="count" select="10" /> > <xsl:param name="base" select="'foo'" /> > <xsl:choose> > <xsl:when test="$count > 1"> > <xsl:call-template name="embedTailRecursive"> > <xsl:with-param name="count" select="$count - 1" /> > <xsl:with-param name="base"> > <foo><xsl:copy-of select="$base" /></foo> > </xsl:with-param> > </xsl:call-template> > </xsl:when> > <xsl:otherwise> > <xsl:copy-of select="$base" /> > </xsl:otherwise> > </xsl:choose> > </xsl:template> > > <xsl:template name="embedNotTailRecursive"> > <xsl:param name="count" select="10" /> > <xsl:param name="base" select="'foo'" /> > <xsl:choose> > <xsl:when test="$count > 1"> > <foo> > <xsl:call-template name="embedNotTailRecursive"> > <xsl:with-param name="count" select="$count - 1" /> > <xsl:with-param name="base" select="$base" /> > </xsl:call-template> > </foo> > </xsl:when> > <xsl:otherwise> > <xsl:copy-of select="$base" /> > </xsl:otherwise> > </xsl:choose> > </xsl:template> > > <xsl:template name="embedDivAndConquer"> > <xsl:param name="count" select="10" /> > <xsl:param name="base" select="'foo'" /> > <xsl:choose> > <xsl:when test="$count = 1"> > <xsl:copy-of select="$base" /> > </xsl:when> > <xsl:when test="not($count mod 2)"> > <foo> > <xsl:call-template name="embedDivAndConquer"> > <xsl:with-param name="count" select="$count div 2" /> > <xsl:with-param name="base" select="$base" /> > </xsl:call-template> > </foo> > <foo> > <xsl:call-template name="embedDivAndConquer"> > <xsl:with-param name="count" select="$count div 2" /> > <xsl:with-param name="base" select="$base" /> > </xsl:call-template> > </foo> > </xsl:when> > <xsl:otherwise> > <foo><xsl:copy-of select="$base" /></foo> > <foo> > <xsl:call-template name="embedDivAndConquer"> > <xsl:with-param name="count" select="($count - 1) div 2" /> > <xsl:with-param name="base" select="$base" /> > </xsl:call-template> > </foo> > <foo> > <xsl:call-template name="embedDivAndConquer"> > <xsl:with-param name="count" select="($count - 1) div 2" /> > <xsl:with-param name="base" select="$base" /> > </xsl:call-template> > </foo> > </xsl:otherwise> > </xsl:choose> > </xsl:template> > > The timings were as follows: > > count Tail Recursive Not Tail Recursive Divide And Conquer > 10 388 393 396 > 50 429 396 396 > 100 451 403 401 > 200 611 418 403 > 500 2666 654 423 > 1000 12726 2241 436 > > As you can see, there's not much in it for low counts, but the time > for the tail recursive template increases exponentially, the > non-tail-recursive template increases more than the divide and conquer > template, which stays roughly the same throughout. > > Of course the real situations where you'd want to nest a string within > even 50 foo elements are pretty far and few between, but it proves > your point. > > That's the last time I let David C. indoctrinate me ;) > > Cheers, > > Jeni > > --- > Jeni Tennison > http://www.jenitennison.com/ > > > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: lookup-table thoughts, David Carlisle | Thread | Re: [xsl] Re: lookup-table thoughts, Jeni Tennison |
Re: [xsl] reliability of MSXML, Daniel Veillard | Date | [xsl] XSL/FOP: Implementing a count, Rachael Blank |
Month |