Deep-equal between sequencesMichael Kay mike at saxonica.com
Wed Jul 11 13:49:51 PDT 2007
> > > > > some $i in $firstSeq satisfies $secondSeq[deep-equal(.,$i)] > > > > Certainly this meets the requirement, and certainly a > half-decent implementation will exit when it finds the first > "true" value. But in the worst case, without a very clever > bit of optimization, it will result in N*M deep-equal comparisons. Come to think of it, it might not be as bad as I thought. The worst case, of doing n^2 deep-equal comparisons, happens when there are no deep-equal pairs, that is, when all the comparisons return false. But when two nodes are not deep-equal, the deep-equal function is likely in most cases to discover this quite quickly: the worst-case performance for deep-equal is when the function returns true. So there could be a situation here that really performs badly, for example when all the nodes are deep-equal in their first 998 children and differ in the 999th, but the cases likely to arise in practice are probably not too bad. It's still O(n^2) though, and can easily be made better. Michael Kay http://www.saxonica.com/
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format