This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: RE: Simple problem - complicated solution
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- To: xsl-list at lists dot mulberrytech dot com
- Date: Thu, 16 May 2002 15:12:54 -0700 (PDT)
- Subject: [xsl] Re: RE: Simple problem - complicated solution
- Reply-to: xsl-list at lists dot mulberrytech dot com
"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.
Cheers,
Dimitre Novatchev.
__________________________________________________
Do You Yahoo!?
LAUNCH - Your Yahoo! Music Experience
http://launch.yahoo.com
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list