This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
RE: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- To: <xsl-list at lists dot mulberrytech dot com>, "'Tom Myers'" <tommy at cs dot colgate dot edu>
- Subject: RE: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- From: "Michael Kay" <michael dot h dot kay at ntlworld dot com>
- Date: Thu, 8 Nov 2001 14:27:08 -0000
- Reply-To: xsl-list at lists dot mulberrytech dot com
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@lists.mulberrytech.com
> [mailto:owner-xsl-list@lists.mulberrytech.com]On Behalf Of
> Jeni Tennison
> Sent: 07 November 2001 18:31
> To: Tom Myers
> Cc: xsl-list@lists.mulberrytech.com
> 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