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