This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
RE: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- To: "'Tom Myers'" <tommy at cs dot colgate dot edu>, <michael dot h dot kay at ntlworld dot com>
- Subject: RE: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- From: "Michael Kay" <michael dot h dot kay at ntlworld dot com>
- Date: Mon, 12 Nov 2001 13:33:13 -0000
- Cc: <xsl-list at lists dot mulberrytech dot com>
- Reply-to: xsl-list at lists dot mulberrytech dot com
> I assume that "O(n^n)" above is a typo for "O(n^2)" = "O(n*n)", right?
yes.
> Quadratic. Let me just check that I understand this from
> Saxon's point of
> view...I'm trying to come up with a simple moral to the tale,
> something
> like "recursion inside constructors should not usually be
> made into tail
> recursions, but other recursions should be", to go along with
> "accumulations
> of associative functions can usually be made into divide-and-conquer
> templates" and other such rules that I often find helpful.
The difference between a tail-recursive linear recursion and a
non-tail-recursive one is that the latter uses less stack space. The moral
of the tail [?], I think, is that unless you're actually running out of
stack space, it's not worth changing an O(n) algorithm into an O(n*n) one in
order to achieve this goal.
But I must look again at whether I can make <xsl:copy-of>, when copying one
RTF to another, do a "virtual copy" that only actually creates a
reference...
Mike Kay
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list