Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once? From: Jeni Tennison <jeni@xxxxxxxxxxxxxxxx> Date: Wed, 7 Nov 2001 18:30:36 +0000 |
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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: lookup-table thoughts, Tom Myers | Thread | Re: [xsl] Re: lookup-table thoughts, David Carlisle |
[xsl] Using position(), Steve Kuntz | Date | Re: [xsl] Using position(), Jeni Tennison |
Month |