RE: Re[4]: Aggregate

Subject: RE: Re[4]: Aggregate
From: Kay Michael <Michael.Kay@xxxxxxx>
Date: Tue, 14 Nov 2000 14:57:56 -0000
> >> So, to find the maximum of the 'in' elements, use:
> >> 
> >>   in[not(parent::TIME/in &gt; .)]
> >
> > But I'd express caution, certainly for large node-sets. 
> This is likely to be
> > an O(n-squared) solution (it certainly is in Saxon).
> 
> Good point.  Would it make any difference if the XPath was:
> 
>   in[not(parent::TIME/in &gt; .)][1]

Yes, Saxon would stop after it found the first one, which on average would
halve the execution time. But it would still be O(n-squared).

> 
> Would the extra positional predicate make the processor (or Saxon at
> least) stop once it found the first instance, and therefore be more
> efficient?  Or what about a mix:
> 
> <xsl:template match="in" mode="find-max">
>   <xsl:variable name="greater"
>                 select="following-sibling::in[. &gt; current()][1]" />
>   <xsl:choose>
>     <xsl:when test="$greater">
>       <xsl:apply-templates select="$greater" />
>     </xsl:when>
>     <xsl:otherwise><xsl:value-of select="." /></xsl:otherwise>
>   </xsl:choose>
> </xsl:template>

This is still O(n-squared). 

> 
> I tend to assume that XPaths are always going to be more efficient
> than using equivalent XSLT instructions because processors have a
> greater opportunity for optimising XPaths, but I guess that's a false
> assumption, especially where there are processor optimisations on
> recursion.

It's certainly possible to optimise the XPath expression you used. (It would
be a bit easier if you wrote ../in rather than parent::TIME/in). But these
optimisations just depend on recognizing common patterns of usage, and as I
said, this is the first time I've seen this one!

Generally, I would assume that XPath expressions aren't optimised unless you
have evidence to the contrary. It's earlier days for optimizers yet. Where
are the research papers being published?


Mike K


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread