[xquery-talk] Deep-equal between sequences

[Michael Kay]

> 
> > 
> > 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/