Subject: [xsl] Efficient Recursive Algorithms in XSLT (Was: Re: Constructing X number of elements) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Tue, 21 Aug 2001 07:42:05 -0700 (PDT) |
Ilkka Hartikainen wrote: > How can I produce X number of elements in XSLT, where X is defined in an > attribute of an element in the source XML file? > > For example (this isn't rally what I'm doing), I have this in the XML: > > <movie name="Alien" rating="3"/> > > And I'd like to produce as many stars as in the rating, like: > > <div> > <img src="star.gif" alt=""/> > <img src="star.gif" alt=""/> > <img src="star.gif" alt=""/> > </div> > > I suppose I can't do this with the for-each-construct. Please help, there > has to be a way for doing this! :) Hi Ilkka, The general solution, which you'll find at all FAQ sites and in the books is to use a recursive (self-calling) named template, which will call itself X - 1 times and on each call will produce the output for just one of the elements -- see for example: http://www.vbxml.com/snippetcentral/main.asp?view=viewsnippet&lang=&id=v20010126065631 This solution will crash some XSLT processors and is generally less efficient (both in time and space) than another general approach for implementing recursive algorithms. The former will require a maximum recursion depth of X, while the latter will have a maximum recursion depth of only Log2(X). Very roughly speaking, you are calling yourself not only once (for the rest of the nod-set), but twice (for the first half and for the second half of the node-set). This idea is generally imployed in the theory of algorithms and has a good, self-describing name: "The Divide and Conquer Principle" (e.g. see "Algorithms in C++ : Parts 1-4 : Fundamentals, Data Structures, Sorting, Searching" by Robert Sedgewick). For an example of such an algorithm implemented in XSLT, see: http://sources.redhat.com/ml/xsl-list/2001-08/msg00248.html http://sources.redhat.com/ml/xsl-list/2001-08/msg00257.html http://sources.redhat.com/ml/xsl-list/2001-08/msg00258.html Thus, a loop for 1000000 elements can be implemented with maximum recursion depth of only 20. This is more than sufficient for most of the practical applications and is not going to crash any of the existing XSLT processors. What is more, a divide and conquer recursive algorithm is proven (and behaves in practice) to be of ***linear complexity*** -- both time and space. This is not the case with the simple one-at-a time algorithms that are typically published in even the best books on XSLT -- in practice they have exponential complexity, because when X increases they very soon start consuming virtual memory (disk swap space). Thus a divide and conquer recursion eliminates the need to use such tricky non-recursive techniques as the one bearing the name of Wendell Piez (see: http://www.vbxml.com/snippetcentral/main.asp?view=viewsnippet&id=v20010324001431 ). Another good feature of recursive algorithms is that their correctness can be proven by mathemathical induction in the same way this is done for proving theorems -- a base that is true, than the inductive step (the recursion). A very important feature of any divide and conquer recursive algorithm is that it can have an extremely efficient implementation ***using parallel processing*** on a multiprocessor system -- the two recursive calls that cover together the whole node-set -- these can be performed not only sequentially, but can be assigned to an available processor each, and executed simultaneously for just half of the time necessary for sequential execution. This is why I am seriously thinking that there should be a new element in the XSLT namespace for explicitly specifying two or more xsl elements in a sequence that may be interpreted parallelly. When I have the time I'll write and publish a generic template for the divide and conquer recursion -- it will be passed a node-set to be processed, as well as template references of "action templates" to produce specific output and "controlling templates" to check for the "stop conditions". More on generic templates can be found at: http://lists.fourthought.com/pipermail/exslt/2001-May/000169.html Hope this helped. Cheers, Dimitre Novatchev. __________________________________________________ Do You Yahoo!? Make international calls for as low as $.04/minute with Yahoo! Messenger http://phonecard.yahoo.com/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] fo:table.. still, Jiri Jirat | Thread | Re: [xsl] Efficient Recursive Algor, Wendell Piez |
[xsl] fo:table.. still, Corey Spitzer | Date | RE: [xsl] Constructing X number of , Chris Bayes |
Month |