Re: In fact it's linear! (Was: Re: [xsl] Summary/Performance/Add Q: convert flat list w/ level information to a hierarcial one?)

[David Tolpin <dvd@xxxxxxxxxxxxxx>]

> 
> Could you, please, provide an xml document on which you think the
> transformation would behave quadratically?
> 

Your test (original test case repeated multiple times) is good.

> > 
> > Please post your data or better mail it to me off-list. This is getting
> > off-topic for the list, I think.
> 
> This is definitely a hot topic, because of number of reasons:
> 
>   1. The problems of writing correct and optimal algorithms are important
> in XSLT development.
> 
>   2. The problems of writing efficient recursive algorithms in XSLT are
> very important.
> 
>   3. There was a reference in one of your messages that exponential times
> are typical of XSLT solutions and a hint.

I was wrong assuming from the analysis of expressions that that grouping algorithm
is exponential, I admitted it; it happened because I made the same error while writing
the expressions and they looked to require a сomputation as many times as there are elements
pending -- that is, the exponential dependency. As there is a cut-off early before the second 
condition, the algorithm is quadratic in most implementations. 

The linear time comes from MSXML because you are probably measuring the time to
output the nodes, not the time to compute. The severe slow down and stack overflow with
the other template comes from MSXML because MSXML most probably  does not turn
tail recursion into a loop.  I don't know whether it happens for any tail recursion or 
for an indirect tail recursion. I suspect that MSXML cannot handle indirect tail recursion,
but didn't get a confirmation yes.

I used a prototype in another language because the other language is more concise
and because it shows explicitely where the result goes. 

David Tolpin

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list