Subject: Re: [xsl] Fibonacci & XSL From: Eric van der Vlist <vdv@xxxxxxxxxxxx> Date: 17 Dec 2002 12:47:57 +0100 |
On Tue, 2002-12-17 at 12:19, Kasper Nielsen wrote: > This is actually more a question of dynamic programming in XSL. > If you can't remember the function it is: > > F0 = 0 > F1 = 1 > f(n)=f(n-1)+f(n-2) for n>=2 > > is it possible to make a template that calculates this in linear time (I > know it can be done in O(lg n) but linear is enogh) in xsl? What about something such as (not tested, may include typos...): <xsl:template name="fibonacci"> <xsl:param name="n"/> <xsl:choose> <xsl:when test="$n <= 0"> <xsl:text>0</xsl:text> </xsl:when> <xsl:when test="$n = 1"> <xsl:text>1</xsl:text> </xsl:when> <xsl:otherwise> <xsl:call-template name="fiboloop"> <xsl:with-param name="fn1" select="1"/> <xsl:with-param name="fn2" select="0"/> <xsl:with-param name="remains" select="$n - 2"/> </xsl:call-template> </xsl:choose> </xsl:template> <xsl:template name="fiboloop"> <xsl:param name="fn1"/> <xsl:param name="fn2"/> <xsl:param name="remains"/> <xsl:variable name="current" select="$fn1 + $fn2"/> <xsl:choose> <xsl:when test="$remains = 0"> <xsl:value-of select="$current"> </xsl:when> <xsl:otherwise> <xsl:call-template name="fiboloop"> <xsl:with-param name="fn1" select="$current"/> <xsl:with-param name="fn2" select="$fn1"/> <xsl:with-param name="remains" select="$remains - 1"/> </xsl:call-template> </xsl:choose> </xsl:template> > The straightforward recursive method for calculating f(n) is clearly > exponential in n. > > If it is possible I would prefer an example using memoization because I need > it to a similar problem I have. For this you would need to store the values already calculated in a variable, use a node-set extension and do a copy-of the previous values at each iteration and this would probably not scale that well. Hope this helps, Eric -- Freelance consulting and training. http://dyomedea.com/english/ ------------------------------------------------------------------------ Eric van der Vlist http://xmlfr.org http://dyomedea.com (W3C) XML Schema ISBN:0-596-00252-1 http://oreilly.com/catalog/xmlschema ------------------------------------------------------------------------ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Fibonacci & XSL, Kasper Nielsen | Thread | RE: [xsl] Fibonacci & XSL, bryan |
Re: [xsl] xsl transform question, Jeni Tennison | Date | RE: [xsl] Fibonacci & XSL, bryan |
Month |