[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
Re: [xsl] Re: How efficient is DVC? - A grouping example
Subject: Re: [xsl] Re: How efficient is DVC? - A grouping example From: "Robbert van Dalen" <juicer@xxxxxxxxx> Date: Sun, 23 Mar 2003 13:25:31 +0100 |
Hi Dimitre, OK, I will drop the Muenchian argument and start focusing on how to build binary trees efficiently. I still think there is an problem with 'linear' DVC in terms of time complexity. If I can show an efficient implementation of building binary trees - then DVC in general can be done efficiently - that's my point. I'll provide complete *working* examples + timings and test them thouroughly *before* posting them to the list ;-) Cheers, Robbert. ----- Original Message ----- From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx> To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx> Sent: Sunday, March 23, 2003 10:56 AM Subject: [xsl] Re: How efficient is DVC? - A grouping example > Hi Robbert, > > Now that it is clear that Muenchian grouping is possible on converted RTFs, > it would probably be best if you can provide another, most simple > non-grouping example of building and using a binary tree as a kind of a more > specific DVC implementation. > > Then, what need be compared is the timings for tree DVC and linear DVC -- > that is when building and using a binary tree and when using just a node-set > and its first and second halves. > > Can you, please, provide such example and also an explanation? > > > ===== > Cheers, > > Dimitre Novatchev. > http://fxsl.sourceforge.net/ -- the home of FXSL > > > > "Robbert van Dalen" <juicer@xxxxxxxxx> wrote in message > news:000701c2f0d9$880fedf0$01000001@xxxxxxxxxxx > > Comparative measurements (on a much slower machine then I've tested on > before) > > Mind you: were grouping N groups ~ N nodes. > > > > I just finished *comparing* the examples: > > > > The first example I tried with 1000 (83 sec) 2000 (320 sec) and 4000 (1200 > sec) > > The second (recursive) example I tried with 1000 nodes and XALAN ran out > of > > stack space. > > The third (binary tree) example I tried with 1000 (34 sec) 2000 (65 sec) > and > > 4000 (150 sec) > > > > So the first example is quadratic > > The second does not apply > > The third is linear but probably O(log(n)*n) > > > > Cheers, > > > > Robbert > > > > > 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 -> |
---|---|---|
[xsl] Re: How efficient is DVC? - A, Dimitre Novatchev | Thread | [xsl] How efficient is DVC? - A gro, Robbert van Dalen |
Re: [xsl] tail recursion optimizati, David Rosenborg | Date | Re: [xsl] How efficient is DVC? - A, Mike Brown |
Month |