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(_at_)yahoo(_dot_)com>
To: <xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com>
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(_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
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list