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. Joel _______________________________________________ xslt mailing list, project page http://xmlsoft.org/XSLT/ [email protected] http://mail.gnome.org/mailman/listinfo/xslt
