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

["Michael Kay" <mike@xxxxxxxxxxxx>]

> 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.

Assuming a competent implementation of xsl:key, Muenchian grouping has O(N
log N) complexity.

By contrast, your algorithm appears to perform N*G/2 comparisons, where N is
the number of items and G the number of groups. This may perform well in the
special case where G is small and independent of N, but in the more general
case G is likely to increase as N increases, which means that your algorithm
approaches O(N^2)

Michael Kay
http://www.saxonica.com/

> 
> 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.
> 
> The example below will group books in a book list and will 
> compute how many
> books each author has (input XML is shown after it).
> 
> <xsl:stylesheet version="1.0"
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
>  <xsl:template match="/booklist">
>   <authors>
>    <xsl:call-template name="RecursiveGrouping">
>     <xsl:with-param name="list" select="book"/>
>    </xsl:call-template>
>   </authors>
>  </xsl:template>
> 
>  <xsl:template name="RecursiveGrouping">
>   <xsl:param name="list"/>
> 
>   <!-- Selecting the first author name as group identifier 
> and the group
> itself-->
>   <xsl:variable name="group-identifier" select="$list[1]/@author"/>
>   <xsl:variable name="group" 
> select="$list[@author=$group-identifier]"/>
> 
>   <!-- Do some work for the group -->
>   <author name="{$group-identifier}" 
> number-of-books="{count($group)}"/>
> 
>   <!-- If there are other groups left, calls itself -->
>   <xsl:if test="count($list)>count($group)">
>   <xsl:call-template name="RecursiveGrouping">
>     <xsl:with-param name="list"
> select="$list[not(@author=$group-identifier)]"/>
>   </xsl:call-template>
>   </xsl:if>
>  </xsl:template>
> </xsl:stylesheet>
> 
> The input XML for this example is the shown below.
> 
> <booklist>
>    <book author="Frank Herbert" title="Dune"/>
>    <book author="Roberto Quaglia" title="Bread, Butter and 
> Paradoxine"/>
>    <book author="Kate Wilhelm" title="Where Late the Sweet 
> Bird Sang"/>
>    <book author="Anthony Burgess" title="A Clockwork Orange"/>
>    <book author="Frank Herbert" title="Dragon in the Sea"/>
>    <book author="Anthony Burgess" title="Earthly Powers"/>
>    <book author="Isaak Asimov" title="The Foundation Trilogy"/>
>    <book author="Frank Herbert" title="Children of Dune"/>
>    <book author="Isaak Asimov" title="The Caves of Steel"/>
> </booklist>
> 
> Sergiu Ignat
> Dynamic Ventures
> www.dyve.com