[xsl] Re: RE: Simple problem - complicated solution

Subject: [xsl] Re: RE: Simple problem - complicated solution
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Thu, 16 May 2002 15:12:54 -0700 (PDT)
"Stuart Celarier" <stuart at ferncrk dot com> wrote:

> The solutions that Joerg presented work correctly, but they are both
> O(n^2) solutions. That is computer-science-speak for the processing 
> time is proportional to the square of number of data elements. No big

> deal for small values of n, but definitely a performance problem as 
> the data set gets big. The second one (with the following-
> sibling::datum in the XPath predicates) takes about half the time of 
> the first one, but it is still proportional to n^2.

> For large sets of data, it would be worth looking at an O(n log n)
> solution, 

[the nice description of a min/max algorithm through sourting skipped]

Hi Stuart,

Probably it would be useful to know that there's an O(N) solution. For
example, this algorithm is implemented by the minimuma() and maximum()
functions of FXSL. Another implementation is a simple recursive named
template -- there is an example of this in Dave Pawson's XSLT FAQ.

Dimitre Novatchev.

Do You Yahoo!?
LAUNCH - Your Yahoo! Music Experience

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

Current Thread