[XSL-LIST Mailing List Archive Home]
[By Thread]
[By Date]
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. -- Cheers, Dimitre Novatchev
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Duplicates in a sequence , Michael Kay mike@xxx | Thread | Re: [xsl] Duplicates in a sequence , Leo Studer leo.stude |
Re: [xsl] Increasing sequence ?, Michael Kay mike@xxx | Date | Re: [xsl] Increasing sequence ?, Dimitre Novatchev dn |
Month |