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]

Simple problem - complicated solution - performance


Dimitre raises an interesting point about using recursion for computing
the minimum and maximum values of a set of data. Let me throw this
question back out to the list, especially to people with XSLT
implementation experience: 

It seems like there must be some practical limits to recursion since
that would involve a call stack in memory. Is it reasonable to think
about recursion that stacks up a couple of thousand or tens of thousands
of calls deep? Taking a page fault on a call stack seems like it could
get very expensive very quickly.

Clearly computing a the minimum and maximum should require linear time,
O(n). But if the computation itself doesn't scale well, then a seemingly
O(n) algorithm could perform much worse in practice. Comments?

Cheers,
Stuart

-----
Dimitre wrote:

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.



 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]