Subject: [xsl] Re: Tail recursion (WAS: Grouping problem?) From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx> Date: Wed, 23 Apr 2003 23:34:43 +0200 |
"Conal Tuohy" <conalt@xxxxxxxxxxxxxxx> wrote in message news:001001c3096e$c36f2700$d9784fcb@xxxxxxxxxxxxxxxxxxxx > Dimitre wrote: > > >You can use a DVC (Divide and Conquer) style algorithm here. Split a > >node-set into two and recursively solve the problem on them. > > <snip/> > > >The recursion depth of a DVC algorithm is only log2(N). > > > >http://www.topxml.com/code/default.asp?p=3&id=v20020107050418 > > OK - log(n) is better than (n), but why use a DVC algorithm to minimise > stack-depth if a tail-recursive algorithm would eliminate the procedure > stack altogether? The reason is simple enough -- why be dependent on unknown and unproven claims and statements about the tail-recursive optimization capabilities of version X of XSLT processor Y, why intentionally destroy the portability of the code and bind it only to a select few XSLT processors? Saxon is a happy exception of the rule, but even in Saxon some cases of tail-recursion optimization are implemented (e.g. recursively calling a named template) while others are not -- see a recent post by Mike Kay explaining this. Using a DVC algorithm it is not meaningful at all to worry about the size of the call stack, therefore not meaningful to try to eliminate it -- the problem simply doesn't exist in any practical case. For example, a DVC 1 MB-string reversal transformation needs a call stack of only 19 elements. Another reason to use DVC is that many DVC algorithms look simpler and more elegant. Look for example at a DVC max(): http://www.topxml.com/code/default.asp?p=3&id=v20030314165921 or at a generic sort: http://www.biglist.com/lists/xsl-list/archives/200303/msg00007.html So I'd reverse your question: Why not implement a DVC algorithm, when it's the only efficiently-working solution in the general case, is much more portable, reliable and aesthetically appealing? ===== Cheers, Dimitre Novatchev. http://fxsl.sourceforge.net/ -- the home of FXSL XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Tail recursion (WAS: Grou, Mike Brown | Thread | RE: [xsl] Re: Grouping problem?, Michael Kay |
[xsl] id Function() Error., Bhandari, Ashish | Date | Re: [xsl] Re: document not there am, J.Pietschmann |
Month |