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

RE: Optimisation (was Re[6]: Aggregate)

Subject: RE: Optimisation (was Re[6]: Aggregate)
From: Kay Michael <Michael.Kay@xxxxxxx>
Date: Fri, 17 Nov 2000 09:48:44 -0000
aggregate xml saxon
> OK. I think my problem lies in the fact that I have never understood
> what 0(n-squared) and so on actually means.

Thanks to Davids Gamboc and Carlisle who have answered the theoretical part
of Jeni's question far better than I could.

> Mike, is it possible for you to sketch out the optimisations in Saxon

The ones that are relevant here are, I suppose, those that find an algorithm
for evaluating an expression that has lower complexity than the naive
algorithm.

Some examples:

$x < $y naively requires X*Y comparisons where X and Y are the cardinalities
of the two node-sets. Saxon evaluates it as min($x) < max($y) which requires
only O(X+Y) operations. It would be possible to optimise $x[not($x > .)]
using the same trick, but Saxon currently doesn't.

xsl:for-each with no xsl:sort naively requires to sort the selected nodes
into document order which would take O(n log n) operations. Saxon goes to
considerable pains to detect cases where the nodes are already naturally
sorted, reducing this to O(n).

$x[1] naively requires a comparison on each element of the list to see if
its position is equal to 1 (so it would be O(X)). Saxon just looks at the
first element, which is O(1).

not($x), where $x is a node-set, naively evaluates the node-set (which is
typically O(X), or even more naively O(X log X) if you were to eliminate
duplicates eagerly) and then tests to see if it is empty (which can be done
in O(1)). Saxon 5.5.1 will usually avoid evaluating the node-set and
eliminating duplicates, but not always, it depends how it is defined.

<xsl:number/> naively requires counting of the nodes that precede a given
node, which requires O(n) operations; therefore numbering a sequence of n
nodes requires O(n^2) operations. Saxon in some cases (but not all)
remembers the last node and its number, so that numbering a sequence of n
nodes becomes O(n).

I'm afraid that's a very incomplete list, but perhaps it gives a flavour.



Mike Kay


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


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

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.
Email
First Name
Last Name
Company
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.