RE: Re: lookup-table thoughts (was Re: matching multip

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