Subject: [xsl] Recursion Was: Re: 2 Questions: (1) about looping... From: Joerg Pietschmann <joerg.pietschmann@xxxxxx> Date: Tue, 28 Aug 2001 12:22:19 +0200 |
Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote: > You can organise a loop in XSLT using either: > > 1. Simple recursion, where a template processes one member of a list and then > calls itself recursively to process the rest -- see for example: [snip] > From the above three, the first works efficiently only on relatively short lists, > getting an exponential-time behaviour very soon when the length of the input list > increases. It also crashes existing XSLT processors (with the exception when > "tail-recursion" and XSLT processors optimised for tail-recursion are used). The > maximum call-stack depth is N - 1. > I have to comment on this. The following code will not crash Saxon even if you start it with i=1000000 and it wont slow down exponentially: <xsl:template name="foo"> <xsl:param name="i"/> <xsl:if test="$i > 0"> <xsl:text>*</xsl:text> <xsl:call-template name="foo"> <xsl:with-param name="i" select="$i - 1"/> </xsl:call-template> </xsl:if> </xsl:template> Some not quite representative execution times as measured by saxon -t (includes some overhead): i time (ms) 10 161 100 170 1000 290 10000 441 100000 5358 1000000 54579 As you see it's somewhat superlinear asymptotically but hardly worth arguing about it. The following variant does the same but will crash already for i=1000 <xsl:template name="bar"> <xsl:param name="i"/> <xsl:if test="$i > 0"> <xsl:variable name="result"> <xsl:text>*</xsl:text> <xsl:call-template name="bar"> <xsl:with-param name="i" select="$i - 1"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="$result"/> </xsl:if> </xsl:template> Optimizing tail recursion implies that local variables must not be held across the recursive invocation. The code above makes it worse by O(n^2) space allocation (the length of the result variable grows linearly, because they are all in memory at the same time this adds up to O(n^2)). Conclusion: properly implemented text-book recursion works, even on large input values/long lists, if the processor is good enough. Divide-and-conquer/binary split techniques may have an adavantage nevertheless due to limited recursion depth, especially if potentially large string buffers are involved. However, the larger overhead of divide-and-conquer techniques is always a disadvantage for small problem sizes. D.Knuth discusses this at length in his famous book series "The Art of Programming", especially in Vol.3 (Sorting and Searching) but also in the "General" section of Vol.1. Interesting comments about traps and pitfalls in tail recursion optimisation can be found in the gcc source code. The Dragon books discuss this also. Regards J.Pietschmann XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
SV: [xsl] Tools for XPath debugging, Jesper Stovby Damgaa | Thread | [xsl] Re: Recursion Was: Re: 2 Ques, Dimitre Novatchev |
SV: [xsl] Tools for XPath debugging, Jesper Stovby Damgaa | Date | Re: [xsl] How do I get MSXML to STO, Michael Beddow |
Month |