Re: [xslt] key() in match pattern of xsl:key

[Vincent Lefevre <vincent+gnome vinc17 org>]

On 2005-12-13 02:03:08 -0500, Joel E. Denny wrote:
> Let's not forget the original problem: compute a key representing a
> set difference.
> 
> I found that the computation is much faster if an intermediate key
> can be referenced. You're suggesting an intermediate RTF instead.
> However, Daniel has previously stated that he will not support keys
> referencing variables, so computing a key from an RTF shouldn't be
> possible.

Unless there's a way, through an extension, to access the RTF in
another way, e.g. with document().

> If you're also suggesting replacing the final key with an RTF, then
> lookup time will worsen from O(1) to O(n). The more information in
> the RTF, the worse.

Not necessarily, but this depends on the XSLT processor. There are
several solutions. First, accessing an ID may be fast; does libxml2
hash the IDs? But a problem is that the processor doesn't necessarily
recognize the IDs (without the xml:id solution, one needs a DTD,
but how to associate a DTD with a RTF? Do libxml2 or libxslt have
another solution?).

Then, you can use standard hashing algorithms. If libxml2 internally
represents the children of an element as an array, then accessing
child number n will be done in O(1). Otherwise you can use a tree,
and if you make sure that it is balanced, the lookup time will be in
O(log n). This isn't as good as O(1), but much better than O(n).

-- 
Vincent Lefèvre <vincent vinc17 org> - Web: <http://www.vinc17.org/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.org/blog/>
Work: CR INRIA - computer arithmetic / SPACES project at LORIA