Altova Mailing List Archives

RE: Re[4]: Aggregate

From: Kay Michael <Michael.Kay@------->
Date: 11/14/2000 2:58:00 PM
> >> 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:


These Archives are provided for informational purposes only and have been generated directly from the Altova mailing list archive system and are comprised of the lists set forth on Therefore, Altova does not warrant or guarantee the accuracy, reliability, completeness, usefulness, non-infringement of intellectual property rights, or quality of any content on the Altova Mailing List Archive(s), regardless of who originates that content. You expressly understand and agree that you bear all risks associated with using or relying on that content. Altova will not be liable or responsible in any way for any content posted including, but not limited to, any errors or omissions in content, or for any losses or damage of any kind incurred as a result of the use of or reliance on any content. This disclaimer and limitation on liability is in addition to the disclaimers and limitations contained in the Website Terms of Use and elsewhere on the site.