This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Implementing Divide and Conquer (Was: Re: Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?)
- To: xsl-list at lists dot mulberrytech dot com
- Subject: [xsl] Implementing Divide and Conquer (Was: Re: Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?)
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- Date: Thu, 8 Nov 2001 20:44:59 -0800 (PST)
- Reply-To: xsl-list at lists dot mulberrytech dot com
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