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

Re: [xsl] Duplicates in a sequence ?


Subject: Re: [xsl] Duplicates in a sequence ?
From: "Leo Studer leo.studer@xxxxxxxxxxx" <xsl-list-service@xxxxxxxxxxxxxxxxxxxxxx>
Date: Fri, 27 Mar 2015 10:58:30 -0000

Michael

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

I agree the above is O(n^2) with no duplicates. However I wonder how
distinct-values is implemented with Saxon that you say it is O(n log n). What
intrigues me is that the order does not change on Oxygen 16.1.

Cheers
Leo


Current Thread
Keywords