xsl-list
[Top] [All Lists]

Re: [xsl] Duplicates in a sequence ?

2015-03-25 14:35:29
On Wed, Mar 25, 2015 at 12:05 PM, Michael Kay mike(_at_)saxonica(_dot_)com
<xsl-list-service(_at_)lists(_dot_)mulberrytech(_dot_)com> wrote:

exists($vSeq[index-of($vSeq,.)[2]][1] )


I think that if there are no duplicates, this is O(n^2), whereas the 
distinct-values solution is O(n log n). Harder to judge how they compare if 
duplicates are more probable: I think this is O(m*n) where n is the size of 
the sequence and m is the expected number of items between two duplicates, 
i.e. m=1/p where p is the probability of an item being a duplicate.

 In the worst case -- yes.

However, if the first item in the sequence has a duplicate, the
evaluation of the expression should be O(N)  -- that is at most n-1
comparison's will be made.


-- 
Cheers,
Dimitre Novatchev
--~----------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
EasyUnsubscribe: http://lists.mulberrytech.com/unsub/xsl-list/1167547
or by email: xsl-list-unsub(_at_)lists(_dot_)mulberrytech(_dot_)com
--~--

<Prev in Thread] Current Thread [Next in Thread>