[XSLLIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Re: lookuptable thoughts (was Re: matching multip
At 02:27 PM 11/8/2001 +0000, Michael Kay wrote: >The reason the tailrecursive 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 nontailrecursive >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 divideandconquer 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 divideandconquer 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(N1)) otherwise <xsl:template name="consRec"> <xsl:param name="N" select="100"/> <xsl:if test="$N"> <X> <xsl:calltemplate name="consRec"> <xsl:withparam name="N" select="$N  1"/> </xsl:calltemplate> </X> </xsl:if> </xsl:template> and if called by <xsl:calltemplate name="consRec"/> it will generate 100 nested Xtags, 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 treedepth is rarely a limiting factor in recursion. Anyway, to do this tailrecursively we do need an accumulator: tailRec(N,A) = A, if N=0 = tailRec(N1,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:copyof select="$A"/></xsl:when> <xsl:otherwise> <xsl:calltemplate name="tailRec"> <xsl:withparam name="N" select="$N  1"/> <xsl:withparam name="A"> <X><xsl:copyof select="$A"/></X> </xsl:withparam> </xsl:calltemplate> </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 "copyof" with "referenceto", 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 "copyof" with something like "referenceto" 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 divideandconquer equivalent is possible in languages with higherorder 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 massivelyparallel proposals for implementations of FP (or FFP) might in fact construct the Ndeep tree in logarithmic time, using linearly many processors, just about as readily as they'd construct an Nlong list the same way. But I'm not sure, not sure at all. Tom Myers XSLList info and archive: http://www.mulberrytech.com/xsl/xsllist

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 awardwinning XML IDE  Download a free trial today! Subscribe in XML format
