Re: Recursive grouping - simple, XSLT 1.0, fast non-M

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.