RE: Re: lookup-table thoughts (was Re: matching multip
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
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format