This is the mail archive of the xsl-list@mulberrytech.com mailing list .


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: RE: Simple problem - complicated solution


"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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]