Re: [xslt] key() in match pattern of xsl:key
- From: "Joel E. Denny" <jdenny ces clemson edu>
- To: The Gnome XSLT library mailing-list <xslt gnome org>
- Subject: Re: [xslt] key() in match pattern of xsl:key
- Date: Mon, 12 Dec 2005 13:38:28 -0500 (EST)
On Mon, 12 Dec 2005, Vincent Lefevre wrote:
> I haven't looked at your specific problem, but I think that *some*
> O(n^2) -> O(n) optimizations can be done with two passes, by storing
> a temporary RTF, that could be used as a nodeset in the second pass.
> With XSLT 1.0, this solution really needs two passes, by calling the
> XSLT processor twice, but with EXSLT, you can use the function that
> converts a RTF into a nodeset.
Thanks for this suggestion. XSLT 1.0 allows variables to reference
variables (so why do the errata prohibit this for keys?) as long as there
are no cycles. I can imagine constructing RTFs for the sets A and B but
sorted by value. That's O(n*log(n)) for each. I can then construct
another RTF for the set AnotB in O(n) time.
The total O(n*log(n)) is better than O(n^2), but lookup time for the final
RTF would be O(n) rather than the O(1) for real keys. Of course, the n
here is much smaller than the n of the original document. Nevertheless, it
would be nice to be able to construct a key off of the final RTF, but keys
referencing variables is prohibited in XSLT 1.0 (even before the errata),
and I've already seen posts from Daniel supporting that rule.
] [Thread Prev