Subject: RE: [xsl] Group on deep equal criterion From: "Vladimir Nesterovsky" <vladimir@xxxxxxxxxxxxxxxxxxxx> Date: Thu, 23 Oct 2008 00:17:03 -0700 |
> Tough one. If you're not worried about O(n^2) performance, you can start by > building a data structure that captures the memberships of the groups by > doing In my case - extraction of common subexpessions from an expression tree - any approach works, as I'm dealing with small sequences. However, out of curiosity for bigger sequences, I was thinking of a quicksort-like xslt algorithm, and x:compare(element(), element()) function returning -1, 0, or 1. In practice this probably won't work well due to expenses of xslt engine comparing with built in algorithms. -- Vladimir Nesterovsky http://www.nesterovsky-bros.com -------- Original Message -------- > From: "Michael Kay" <mike@xxxxxxxxxxxx> > Sent: Wednesday, October 22, 2008 11:10 AM > To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx > Subject: RE: [xsl] Group on deep equal criterion > > Tough one. If you're not worried about O(n^2) performance, you can start by > building a data structure that captures the memberships of the groups by > doing > > <xsl:for-each select="$in"> > <xsl:variable name="x" select="."/> > <item id="generate-id()"> > <xsl:for-each select="$in[deep-equal(., current())]"> > <duplicate id="{generate-id()}"/> > </xsl:for-each> > </item> > </xsl:for-each> > > You can then use conventional grouping to identify the distinct groups (not > trivial, but I assume you can solve that one), and use > > <xsl:key name="gid" match="*" use="generate-id()"/> > > to get back from the generated ids to the original nodes. > > If you are worried about O(n^2) performance, but don't want to resort to > extensions, then you can try and define a hash function that will give the > same result for two nodes if they are deep-equal. You can then modify the > above to start by doing value-based grouping on the hash key, and then apply > the O(n^2) logic only within each of these groups. A simple but quite > effective hash key might be something like concat(count(.//*), string(.)). > > (Of course this still has O(n^2) performance in the worst case where all the > input nodes are deep-equal to each other, but one assumes that case is > unlikely). > > Michael Kay > http://www.saxonica.com/ > > > > -----Original Message----- > > From: Vladimir Nesterovsky [mailto:vladimir@xxxxxxxxxxxxxxxxxxxx] > > Sent: 22 October 2008 07:50 > > To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx > > Subject: [xsl] Group on deep equal criterion > > > > Hello! > > > > What is the best way to group elements by deep-equal() criterion?
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Group on deep equal crite, Michael Kay | Thread | [xsl] Content of Script element get, Joyce Babu |
Re: [xsl] Content of Script element, Joyce Babu | Date | Re: [xsl] Content of Script element, Joyce Babu |
Month |