[xsl] Re: Exslt implementation, was "When does sort occur?"

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

> You could also of course just write a template directly that iterates
> along a parameter containing the node set, and passing on a parameter
> with the largest value so far.
>
> Any of these solutions is likely to just have to make one pass over the
> data to fond the largest so will have time proportional to the n if
> there are n nodes to be accessed.
>
> using xsl:sort and taking the first  requires less keystrokes to code in
> xslt but will always take longer given a large enough data set (unless
> you have a very smart query optimiser) as you first sort all the nodes
> into a complete order and then ignore most of that information and just
> take the first. You can not sort a list of values in order n time, most
> likely it takes n log n.


This is so.

Interestingly, I have not been able to construct an example (regardles of
the length of the node-set) when the xsl:sort - based algorithm is actually
slower than the linear solutions.

O(N) and O(log(N) * N)  both have a some coefficient at the front -- 
obviously the one for the liner solutions is quite big.



=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL




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