Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once? From: Tom Myers <tommy@xxxxxxxxxxxxxx> Date: Thu, 08 Nov 2001 19:24:00 -0500 |
Jeni Tennison wrote >Mike Kay wrote: > > 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. >Gah, yes, my idiocy. Dimitre, can you see a way of using a divide >and conquer algorithm to produce a multiply-nested tree? ><xsl:call-template name="accumDivAndConquer"> ><xsl:with-param name="count" select="3" /> ><xsl:with-param name="base" select="'foo'" /> ></xsl:call-template> >producing: ><foo> ><foo> ><foo>foo</foo> ></foo> ></foo> >Jeni >- --- and probably Dimitre has already answered (I'm on digest) but here's one version, based on the idea that dC(5,"foo") = <X><X><X><X><X>foo</X></X></X></X></X> via dC(0,A) = A dC(2*N,A) = dC(N,dC(N,A)) dC(2*N+1,A) = dC(N, dC(N, cons("X",A) ) ) so I expect stack depth to be O(log(N)), time to be O(N^2), max space to be O(N), space allocation to be O(N^2)...rather like the tail-recursive except for O(log(N)) instead of O(1) stack space, and of course not needing anything special in the engine. ------------------------------ <xsl:template name="divConq"> <xsl:param name="N" select="10"/> <xsl:param name="A" select="/.."/> <xsl:param name="Ndiv2" select="($N - $N mod 2) div 2"/> <xsl:choose> <xsl:when test="not($N)"><xsl:copy-of select="$A"/></xsl:when> <xsl:otherwise> <xsl:variable name="onebase"> <xsl:choose> <xsl:when test="$N mod 2"> <X><xsl:copy-of select="$A"/></X> </xsl:when> <xsl:otherwise> <xsl:copy-of select="$A"/> </xsl:otherwise> </xsl:choose> </xsl:variable> <xsl:variable name="halfway"> <xsl:call-template name="divConq"> <xsl:with-param name="N" select="$Ndiv2"/> <xsl:with-param name="A" select="$onebase"/> </xsl:call-template> </xsl:variable> <xsl:call-template name="divConq"> <xsl:with-param name="N" select="$Ndiv2"/> <xsl:with-param name="A" select="$halfway"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> ---------------------------------------- hope that makes sense... Tom Myers XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] How can I improve this, Jeni Tennison | Thread | [xsl] Generating new element whose , Hyun Sung Chang |
[xsl] How can I improve this, Walter Torres | Date | [xsl] Generating new element whose , Hyun Sung Chang |
Month |