[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Optimisation (was Re[6]: Aggregate)
> 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
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|