Subject: RE: Optimisation (was Re[6]: Aggregate) From: Kay Michael <Michael.Kay@xxxxxxx> Date: Fri, 17 Nov 2000 09:48:44 0000 
> OK. I think my problem lies in the fact that I have never understood > what 0(nsquared) 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 nodesets. 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:foreach 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 nodeset, naively evaluates the nodeset (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 nodeset 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 XSLList info and archive: http://www.mulberrytech.com/xsl/xsllist
Current Thread 


< Previous  Index  Next > 

Re: Unicode Enitity •, Robert Koberg  Thread  Re: Optimisation (was Re[6]: Aggreg, David Carlisle 
Re: ANN: XSLTDoc Alpha, Michel Goossens  Date  Re: ANN: XSLTDoc Alpha, David Carlisle 
Month 