[xsl] Efficient Recursive Algorithms in XSLT (Was: Re: Constructing X number of elements)

[Dimitre Novatchev <dnovatchev at yahoo dot com>]

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