Subject: Re: [xsl] Re: HOWTO: convert flat list w/ level information to a hierarchial one?u From: andrew.curry@xxxxxxxxxxxx Date: Wed, 3 Dec 2003 11:10:27 -0000 |
>From the data given the relationship is exponential not quadratic. ----- Original Message ----- From: "David Tolpin" <dvd@xxxxxxxxxxxxxx> To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx> Sent: Wednesday, December 03, 2003 10:48 AM Subject: Re: [xsl] Re: HOWTO: convert flat list w/ level information to a hierarchial one?u > > >Look, the time is exponential. > > > > I'll believe that it's quadratic, but I think it's most unlikely to be > > exponential. > > > > O(2^n) is not the same as O(n^2)! > > > > If data is two times longer, the computation time is 4 times longer with quadratic > dependence, right? With the alogirthm that uses unlimited lookahead it is > 100 ms for 100 nodes > 1000 ms for 200 nodes > according to Dimitre's data. > > My testing environment is 100 times slower. > > 10 s for 100 nodes > 32 s for 150 nodes > 120 s for 200 nodes > 350 s for 250 nodes > 920 s for 300 nodes > > Looks like exponential. Time grows 3 times with each additional 50 nodes. > This is with SAXON 6.5.3, JDK 1.3.1/FreeBSD, Pentium II 700MHz. Deviations > are due to garbage collection, I think. > > Although I was never formally taught the theory of algorithms, I will try to provide > a formal proof. > > David > > > > > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list > XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: HOWTO: convert flat l, David Tolpin | Thread | Re: [xsl] Re: HOWTO: convert flat l, David Tolpin |
Re: [xsl] Summary/Performance/Add Q, David Tolpin | Date | RE: [xsl] creating a string of chil, Haydn Flower |
Month |