xsl-list
[Top] [All Lists]

Re: How efficient is DVC? - A grouping example

2003-03-23 02:56:23
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(_at_)xs4all(_dot_)nl> wrote in message
news:000701c2f0d9$880fedf0$01000001(_at_)smartass(_dot_)(_dot_)(_dot_)
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