xsl-list
[Top] [All Lists]

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

2003-12-03 08:30:58

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