[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

RE: [xsl] finding out distinct node/values


Subject: RE: [xsl] finding out distinct node/values
From: "Michael Kay" <mike@xxxxxxxxxxxx>
Date: Wed, 10 Feb 2010 17:33:09 -0000

> And, please, hit me over the head: where is the second
> (hidden?) loop that would make this O(n^2)?

One loop is the /table/rows/row/name, the other is the preceding::name.

Not sure which you regard as being "hidden".

(Interestingly, I came across a case recently where this performed rather
well: it was a case where there were very few distinct values, and therefore
most values were rejected very quickly as duplicates. But that's unusual.)

Regards,

Michael Kay
http://www.saxonica.com/
http://twitter.com/michaelhkay
>
> -W
>
> On Wed, Feb 10, 2010 at 6:11 PM, Andrew Welch
> <andrew.j.welch@xxxxxxxxx> wrote:
> >
> > Hi,
> >
> > > <xsl:stylesheet version="1.0"
> > >  xmlns:xsl="http://www.w3.org/1999/XSL/Transform" >
> > >  <xsl:template match="/">.
> > >    <xsl:for-each select="/table/rows/row/name">
> > >      <xsl:if test="not(. = preceding::name)">
> > >        <xsl:copy-of select="."/>
> >
> > While this is perfectly fine, it's worth being aware that
> its On^2....
> > in other words, as n (the number of elements that are selected)
> > increases by 1, it will have to check every other element in the
> > set.... which means it will perform badly for large values of n.
> >
> >
> > --
> > Andrew Welch
> > http://andrewjwelch.com
> > Kernow: http://kernowforsaxon.sf.net/


Current Thread