[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] Duplicates in a sequence ?

Subject: Re: [xsl] Duplicates in a sequence ?
From: "Michael Kay mike@xxxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Wed, 25 Mar 2015 19:05:16 -0000

On 25 Mar 2015, at 17:02, Dimitre Novatchev dnovatchev@xxxxxxxxx
<xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx> wrote:

> And if you just need the boolean  (true()/false()) indicating whether
> a sequence has duplicate values -- not needing the values themselves
> -- then use the following, slightly adjusted and more efficient
> expression:
> 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.

Michael Kay

Current Thread