Subject: [xsl] Implementing Divide and Conquer (Was: Re: Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Thu, 8 Nov 2001 20:44:59 -0800 (PST) |
Tom Myers <tommy at cs dot colgate dot edu> wrote > 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... Hi Tom, It makes sence and it works. The good news is that you're seemingly avoiding the problem-specific re-combinatiion of the partial results (I'm still not convince that this can be generally done for any problem -- see the examples in my previous post). The bad news is that your solution cannot be executed in parallel -- at least not with a language that doesn't have lazy evaluation. It is interesting if somebody can check whether ghc will parallelize your dvc definition. Cheers, Dimitre Novatchev. __________________________________________________ Do You Yahoo!? Find a job, post your resume. http://careers.yahoo.com XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Generating new element wh, bernwardhanssen | Thread | Re: [xsl] Implementing Divide and C, Colin Paul Adams |
[xsl] Href, Seema | Date | RE: [xsl] Href, Joshua . Kuswadi |
Month |