Re: [xsl] Re: How efficient is DVC? - A grouping example

["Robbert van Dalen" <juicer@xxxxxxxxx>]

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