Re: [xsl] Duplicates in a sequence ?

Subject: Re: [xsl] Duplicates in a sequence ?
From: "Dimitre Novatchev dnovatchev@xxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Wed, 25 Mar 2015 19:35:15 -0000
On Wed, Mar 25, 2015 at 12:05 PM, Michael Kay mike@xxxxxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> 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.

Dimitre Novatchev

Current Thread