Subject: In fact it's linear! (Was: Re: [xsl] Summary/Performance/Add Q: convert flat list w/ level information to a hierarcial one?) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Wed, 3 Dec 2003 05:42:13 -0800 (PST) |
> 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
[xsl] Dimitre's algorithm, fixed: q, David Tolpin | Thread | Re: In fact it's linear! (Was: Re: , David Tolpin |
Re: [xsl] creating a string of chil, David Carlisle | Date | [xsl] XSL stylesheet syntax help, dan |
Month |