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



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/



[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]