[xquery-talk] Deep-equal between sequences
Michael 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/
More information about the talk
mailing list