[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

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

Subject: RE: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
From: Tom Myers <tommy@xxxxxxxxxxxxxx>
Date: Thu, 08 Nov 2001 13:59:37 -0500
o n 2 matching
At 02:27 PM 11/8/2001 +0000, Michael Kay wrote:
>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.

I assume that "O(n^n)" above is a typo for "O(n^2)" = "O(n*n)", right?
Quadratic. Let me just check that I understand this from Saxon's point of
view...I'm trying to come up with a simple moral to the tale, something 
like "recursion inside constructors should not usually be made into tail 
recursions, but other recursions should be", to go along with "accumulations
of associative functions can usually be made into divide-and-conquer
templates" and other such rules that I often find helpful. Simplifying Jeni's 
templates slightly, I do a constructor recursion like so:

  consRec(N) =  [],                      if N=0
                cons("X", consRec(N-1))  otherwise

<xsl:template name="consRec">
   <xsl:param name="N" select="100"/>
   <xsl:if test="$N">
      <X>
        <xsl:call-template name="consRec">
          <xsl:with-param name="N" select="$N - 1"/>
        </xsl:call-template>
      </X>
   </xsl:if>
</xsl:template>

and if called by <xsl:call-template name="consRec"/> it will generate 100
nested X-tags, the innermost being empty, and Saxon will do this in O(n)
time, O(n) stack space, and O(n) heap space -- whereas a lazy implementation
would still need O(n) time and O(n) heap space but O(1) stack space, since
it would return the top of the tree without waiting for the bottom. This is
not, however, an argument for a lazy evaluator, since actual tree-depth
is rarely a limiting factor in recursion. Anyway, to do this tail-recursively 
we do need an accumulator:

   tailRec(N,A) = A, if N=0
                  = tailRec(N-1,cons("X",A)) otherwise

<xsl:template name="tailRec">
   <xsl:param name="N" select="100"/>
   <xsl:param name="A" select="/.."/>
   <xsl:choose>
     <xsl:when test="not($N)"><xsl:copy-of select="$A"/></xsl:when>
     <xsl:otherwise>
       <xsl:call-template name="tailRec">
          <xsl:with-param name="N" select="$N - 1"/>
          <xsl:with-param name="A">
           <X><xsl:copy-of select="$A"/></X>
          </xsl:with-param>
       </xsl:call-template>
    </xsl:otherwise>
   </xsl:choose>
</xsl:template>

And Saxon will do this in O(n^2) time, O(1) stack space, and O(n) max
heap requirement but O(n^2) total heap allocation, whereas if you 
could somehow replace "copy-of" with "reference-to", using the fact
that the accumulator $A is only used once on any computation path,
then you'd have O(n) time, O(1) stack, O(n) max heap.

My main question is "hey, is this right for Saxon?" but I'd like to
know also -- is such a replacement of "copy-of" with something like
"reference-to" possible in principle, or does it violate some XSLT
principle of which trees go where, or...?

As a distinctly stranger thought, to which you will probably not feel
like responding but Dimitre might:

You note that Jeni's divconq version doesn't generate the same output.
A divide-and-conquer equivalent is possible in languages with higher-order
functions; if we think of consX(a) = cons("X",a) as a function, then
tailRec(N) = divConq(N) = consX(consX(consX(... ([]) ...))) and we get
   divConq(N) = dC(N)([])
where
     dC(0)(a) = a 
     dC(1)(a) = consX(a) =  cons("X",a)  and so on,
in other words
     dC(0) = IdentityFunction
     dC(2*N) = compose(dC(N),dC(N))
     dC(2*N + 1) = compose(dC(N),compose(dC(N),consX));
and divConq works just like foldL and foldR (because function composition
is associative). I admit I'm thinking back to Backus' FP systems, wherein
function composition was one of the primitives (but application was not.)
I think that some of the massively-parallel proposals for implementations
of FP (or FFP) might in fact construct the N-deep tree in logarithmic time,
using linearly many processors, just about as readily as they'd construct
an N-long list the same way. But I'm not sure, not sure at all.

Tom Myers


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


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.