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

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