[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

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

Subject: Re: Recursive grouping - simple, XSLT 1.0, fast non-Muenchian grouping method
From: Dimtre Novatchev <dnovatchev@xxxxxxxxx>
Date: Tue, 21 Dec 2004 06:57:46 +1100
grouping in xsl 1.0
We might have some terminological problem here.

What is "Muenchian grouping without xsl:key" ?


On Mon, 20 Dec 2004 19:47:07 +0200, Sergiu Ignat <sergiu.ignat@xxxxxxxx> wrote:
> Hello Dimitre,
> The presented algorithm works much faster than Muenchian grouping without
> xsl:key for a large xml of about 720 elements that sould be grouped in
> groups of 1 to 5 elements per group, up to 5 times faster in that particular
> case.(If you want I can send you the input samples, they are too large to be
> sent to the group). It works slower than Muenchian method with xsl:key and
> generate-id(). The same recursive grouping can be implemented using xsl:key.
> It is much faster than the previous version but it is still a bit slower
> than Muenchian method with xsl:key and generate-id().
> The advantage of recursive grouping is that it is possible to define
> grouping rules that are much more complex than one accepted by the use
> attribute of xsl:key or by generate-id() function. For example if in a list
> of items that have attributes price and quantity the grouping should be done
> by price*quantity.
> Using any of this 2 methods it is also possible to generate a sorted output.
> In that case instead of selecting the grouping identifier of the first
> element in the list it is necessary to select the min or max grouping
> identifier value.
> We are using XSL for reporting, and sometimes grouping rules are very
> complex.
> A recoursive grouping with xsl:key is presented below.
> <?xml version="1.0" encoding="UTF-8" ?>
> <xsl:stylesheet version="1.0"
> xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
> <xsl:key name="title-search" match="book" use="@author" />
> <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="key('title-search',$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 xml input is:
> <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>
> ----- Original Message -----
> From: "Dimtre Novatchev" <dnovatchev@xxxxxxxxx>
> To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>
> Cc: "Sergiu Ignat (dyve)" <sergiu.ignat@xxxxxxxx>
> Sent: Saturday, December 18, 2004 12:49 AM
> Subject: Re:  Recursive grouping - simple, XSLT 1.0, fast non-Muenchian
> grouping method
> 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)?

Current Thread


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.