Subject: Re: [xsl] Re: HOWTO: convert flat list w/ level information to a hierarchial one?u From: David Tolpin <dvd@xxxxxxxxxxxxxx> Date: Wed, 3 Dec 2003 14:48:56 +0400 (AMT) |
> >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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Re: HOWTO: convert flat l, Michael Kay | Thread | Re: [xsl] Re: HOWTO: convert flat l, andrew . curry |
[xsl] Summary/Performance/Add Q: c, Marcus Zelezny | Date | Re: [xsl] Summary/Performance/Add Q, David Tolpin |
Month |