[xsl] An efficient repeat() template (Was: RE: Re: RE: creating a string of repeated charactors)

[Dimitre Novatchev <dnovatchev at yahoo dot com>]

Tim Watts wrote:

> Thanks Dimitre,
> 
> for the more terse code.
> 
> Unfortumatly I do not know the max value (N) so the code won't be usefull
> for me this time.

-----Original Message-----
From: Dimitre Novatchev

Tim Watts wrote:

[snip]

> The EXSLT function <xsl:value-of select="str:padding(10, '*')" /> function
> is the sort of thing I hoped might exist in *standard* XSLT.
>
> Since there isn't I'll use the template that you pointed me to instead.
> (Thanks for saving me from writing it! :) )
>
> I was hoping that there might me a less verbose way of doing what really
is
> quite a simple task.

> > This template is "verbose" by necessity -- it solves the ***general*** case,
> > when
> > neither the filling characters, nor an upper limit for the length are known
> > in
> > advance.
> > 
> > It is also quite space-consuming (and time) -- because the string length is
> > doubled
> > until a larger string is constructed, this will use twice as much memory, as
> > necessary for the resulting string.
> > 
> > In many cases one knows in advance that he'll only need a string of upto N
> > characters.


Hi Tim,

I'm glad to be able to provide an efficient repeat() template. As can be seen
from the code below, care was taken to use very little amount of memory and to
decrease recursion depth to a reasonable value.

This template uses the same idea of a pre-coded concatenation of the $str parameter
N times (I chose N=15), and calls itself recursively to get a new expanded string, k
times longer that the original, where

k = ActualTimes/N

Here's the code:

    <xsl:template name="repeat">
      <xsl:param name="str" select="'.'" />
      <xsl:param name="times" select="1"/>

       <xsl:variable name="skeleton"
       select="concat($str,$str,$str,$str,$str,
                      $str,$str,$str,$str,$str,
                      $str,$str,$str,$str,$str)"/>

       <xsl:variable name="strLength" select="string-length($str)"/>

       <xsl:variable name="actualTimes"
                     select="string-length($skeleton)
                            div
                             $strLength"/>
       <xsl:choose>
         <xsl:when test="$times &lt;= $actualTimes">
           <xsl:value-of select="substring($skeleton, 1, $times * $strLength)"/>
         </xsl:when>
         <xsl:otherwise>
           <xsl:variable name="quotient"
                         select="ceiling($times div $actualTimes)"/>

           <xsl:variable name="strEnlarged">
              <xsl:call-template name="repeat">
                <xsl:with-param name="str" select="$str"/>
                <xsl:with-param name="times" select="$quotient"/>
              </xsl:call-template>
           </xsl:variable>

           <xsl:variable name="longEnoughString">
              <xsl:call-template name="repeat">
                <xsl:with-param name="str" select="$strEnlarged"/>
                <xsl:with-param name="times" select="$actualTimes"/>
              </xsl:call-template>
           </xsl:variable>

           <xsl:value-of select="substring($longEnoughString, 
                                           1,
                                           $times * $strLength)"/>
         </xsl:otherwise>
       </xsl:choose>
    </xsl:template>

I run this template as follows:

      <xsl:call-template name="repeat">
         <xsl:with-param name="str" select="concat('*******', '&#xA;')"/>
         <xsl:with-param name="times" select="32000"/>
      </xsl:call-template>

This produces a string of 256000 characters (32000 lines of 8 characters each).

The total memory, that is requested during the transformation by the "repeat"
template to produce the result is only 259200 bytes.

Its maximum recursion depth is 3.

In contrast, the exslt str:padding() template, when instantiated to produce the same
result:

  <xsl:call-template name="str:padding">
    <xsl:with-param name="length" select="256000"/>
    <xsl:with-param name="chars" select="concat('*******', '&#xA;')" />
  </xsl:call-template>

produces requests for 708750 additional bytes.

Its maximum recursion depth is 10.

I also compared the speed of using these two templates. The tricky part was to
eliminate the time of writing the final string result to the output -- this may
severely distort the correct times.

For this purpose for my template I introduced an outermost template, in which the
result is assigned to a xsl:variable and not output.

I made a similar change to the str:padding template.

The results of running these two templates to produce the result of 256000 bytes as
described above is:

repeat()      -- 67 to 73 milliseconds (50 to 53 if I hardcode 15 for $ActualTimes)

str:padding() -- 130 to 150 milliseconds

Therefore repeat() is about 2.8 times as fast as str:padding()

Also, the repeat() template requires almost 3 times less memory and has a 3 times
smaller recursion depth than the str:padding() template.

By carefully choosing N (the number of times the parameter string is concatenated to
itself in the template) an even better result may be possible.

This time was the "execution" time measured by using the -t option of msxsl.exe on a
P-266 128MB
computer.

Taking into account also the document and stylesheet load time and the compile time,
we need to add 40 milliseconds to the timings of the repeat() template and 35
milliseconds to the timings of the str:padding() template. However these happen only
once per the runtime of a stylesheet, while the templates may be called many times,
so it is reasonable to compare just the "execution time". 


Recently Jim Fuller wrote:
"maybe efficient coding is an artiface( analogous to our use of assignment
statements and gotos once were when making the functional programming
leap..) born through limitations of our current hardware ( not to mention
having only 10 fingers for inputting ), maybe we will find that through
incredibly complicated, error ridden, poorly constructed, trillion line
programs we will find richer and greater expressions of functionality.

i suspect that programmers will turn into farmers soon enough."

I hope it is clear why I strongly disagree with this statement.

Cheers,
Dimitre Novatchev.


__________________________________________________
Do You Yahoo!?
Get personalized email addresses from Yahoo! Mail
http://personal.mail.yahoo.com/

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list