thanks to Michael Kay, I have discovered that however expressions in the
Dimitre's algorithm lead to exponential time, they are incorrect. I hope
that this corrected version of Dimitre Novachev's algorithm both
produces the correct result and has quadratic time. The changes are
around line the second following-sibling:: expression.
David,
Thank you very much for the correction.
I ran the transformations and now am getting the following results in
milliseconds:
No. nodes David's Dimitre's (with David's correction)
==============================================================
100 15 - 40 4.5 - 6
200 48 - 80 7.6 - 9.126
400 114 - 180 16 - 23
800 442 - 673 32 - 57
1600 1207 - 1791 66 - 105
3200 Stack Overflow 142 - 233
In fact, this transformation exhibits linear runtime behaviour!
As for the potential problem with your transformation -- it is obvious
from the results.
Thank you once again. I am glad that I was right to prefer the more simple
algorithm -- isn't small beautiful? :o)
=====
Cheers,
Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
__________________________________
Do you Yahoo!?
Free Pop-Up Blocker - Get it now
http://companion.yahoo.com/
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list