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[(_at_)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
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--