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

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

> 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