Re: Re: How efficient is DVC? - A grouping example
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: 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
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format