Re: [xml] xpath - descendant::something versus */something performance

[Daniel Veillard <veillard redhat com>]

On Fri, Jun 11, 2004 at 01:20:10PM +0200, Petr Pajas wrote:
> First, what is the difference between these two: the code indicates
> that the latter assumes that the node-sets are disjoint, right?  Can

  Right. Adding and removing doublons from a list is O(n) if not sorted.
Adding to a list without constraints is O(1). The major cost difference
is aboslutely normal.

> xmlXPathNodeSetMergeUnique be used for AXIS_DESCENDANT and
> AXIS_DESCENDANT_OR_SELF as well? (I probed if it would speed

  I'm afraid it won't work. It work if starting from an unique node.
If you start from 2 nodes and they are not on disjoint subtree this
would break XPath semantic and XSLT. 

> descendant::form and it did, but maybe the change is semantically
> incorrect). Alternatively, is there some space for optimization in
> xmlXPathNodeSetMerge?

  I think I tried to optimize it a lot especially based on the node
ordering. You might be able to do better, but I don't have a clear idea
how. It's gonna be at best O(log(n)) anyway.

Daniel


-- 
Daniel Veillard      | Red Hat Desktop team http://redhat.com/
veillard redhat com  | libxml GNOME XML XSLT toolkit  http://xmlsoft.org/
http://veillard.com/ | Rpmfind RPM search engine http://rpmfind.net/