Re: [xsl] Recursive grouping - simple, XSLT 1.0, fast non-Muenchian grouping method

[Geert Josten <Geert.Josten@xxxxxxxxxxx>]

Hi,

<M:D/> is performing tests. See yesterdays thread "Test code and results comparing Muenchian Method 
with the method suggested by Sergiu Ignat" by <M:D/> in which he refers to the following page:

	http://www.xsltblog.com/archives/2004/12/new_alternative.html

:-)

Grt(z)

Dimtre Novatchev wrote:

> On Thu, 16 Dec 2004 19:27:46 +0200, Sergiu Ignat (dyve)
> <sergiu.ignat@xxxxxxxx> wrote:
>
> > Hello everybody.
> >
> > I would like to present you a simple, XSLT 1.0, fast grouping method with a
> > O(N*log(N)) complexity, the same as sorting. The only grouping method I knew
> > so far is Muenchian that has O(N^2) complexity.
>
>
> The complexity of the Muenchian method is much better than O(N^2) --
> can you provide an example with representative data, where the
> Muenchian method behaves O(N^2)?
>
>
>
>
> > The main idea is to have a named template that takes as a parameter the node
> > list that should be grouped, processes the group defined by the first
> > element and recursively calls itself for the rest of the list excluding that
> > group.
>
>
> Yes, and this will be close to O(N^2) complexity, where N is the
> number of nodes that are being grouped.
>
> Once again -- can you provide evidence to a better performance?
>
> Cheers,
> Dimitre.

--
Geert.Josten@xxxxxxxxxxx
IT-consultant at Daidalos BV, Zoetermeer (NL)

http://www.daidalos.nl/
tel:+31-(0)79-3316961
fax:+31-(0)79-3316464

GPG: 1024D/12DEBB50