Ordering long vectors

I need to order a long vector of integers with rather few unique values.
This is very slow:

x <- sample(rep(c(1:10), 50000))
system.time(ord <- order(x))

[1] 189.18   0.09 190.48   0.00   0.00

But with no ties

y <- sample(500000)
system.time(ord1 <- order(y))

[1] 1.18 0.00 1.18 0.00 0.00

it is very fast!
This gave me the following idea: Since I don't care about keeping the 
order within tied values, why not add some small disturbance to  x,
and indeed,

unix.time(ord2 <- order(x + runif(length(x), -0.1, 0.1)))

[1] 1.66 0.00 1.66 0.00 0.00

system.time(ord3 <- order(x + seq(0, 0.9, length = length(x))))             

On Sat, 7 Jun 2003, Göran Broström wrote:

I need to order a long vector of integers with rather few unique values.
This is very slow:

x <- sample(rep(c(1:10), 50000))
system.time(ord <- order(x))

[1] 189.18   0.09 190.48   0.00   0.00

But with no ties

y <- sample(500000)
system.time(ord1 <- order(y))

[1] 1.18 0.00 1.18 0.00 0.00

it is very fast!
This gave me the following idea: Since I don't care about keeping the
order within tied values, why not add some small disturbance to  x,

system.time(a<-sapply(sort(unique(x)),function(i) which(x==i)))

I need to order a long vector of integers with rather few unique values.
This is very slow:

aa<-sample(rep(1:10,50000))
system.time( order(aa, 1:length(aa)))

system.time( order(aa))

On Sat, 7 Jun 2003, [ISO-8859-1] G?ran Brostr?m wrote:

I need to order a long vector of integers with rather few unique values.
This is very slow:

I think the culprit is

src/main/sort.c: orderVector1

    /* Shell sort isn't stable, but it proves to be somewhat faster
       to run a final insertion sort to re-order runs of ties when
       comparison is cheap.
    */

This also explains:

aa<-sample(rep(1:10,50000))
system.time( order(aa, 1:length(aa)))

[1] 3.67 0.01 3.68 0.00 0.00

system.time( order(aa))

^C
Timing stopped at: 49.33 0.01 49.34 0 0

which is perhaps the simplest work-around :).

On Sun, 8 Jun 2003, Thomas Lumley wrote:

On Sat, 7 Jun 2003, [ISO-8859-1] G?ran Brostr?m wrote:

I need to order a long vector of integers with rather few unique values.
This is very slow:

I think the culprit is

src/main/sort.c: orderVector1

    /* Shell sort isn't stable, but it proves to be somewhat faster
       to run a final insertion sort to re-order runs of ties when
       comparison is cheap.
    */

This also explains:

aa<-sample(rep(1:10,50000))
system.time( order(aa, 1:length(aa)))

[1] 3.67 0.01 3.68 0.00 0.00

system.time( order(aa))

^C
Timing stopped at: 49.33 0.01 49.34 0 0

which is perhaps the simplest work-around :).

Hello Mr Ripley,

i was waiting you to ask and if you don't mind if there is a fast way in R to do these loops made with R and that takes a week because my matrix is with thousand of rows.
I got another method that is more fast and is utilised by many packages : interfacing with other languages", but it is only a question for information 
 

foo<-function()
 {for (i in 1:(n-1)){
   for (k in (i+1):n){ 
   b_0
   for (j in 1:m){
    if(bin[i,j]==TRUE&bin[k,j]==TRUE) b_b+1}
         print (b)
 } 
     }
  }

Thanks a lot
Ramzi

On Sun, 8 Jun 2003, G?ran Brostr?m wrote:

On Sun, 8 Jun 2003, Thomas Lumley wrote:

On Sat, 7 Jun 2003, [ISO-8859-1] G?ran Brostr?m wrote:

I need to order a long vector of integers with rather few unique values.
This is very slow:

I think the culprit is

src/main/sort.c: orderVector1

    /* Shell sort isn't stable, but it proves to be somewhat faster
       to run a final insertion sort to re-order runs of ties when
       comparison is cheap.
    */

This also explains:

aa<-sample(rep(1:10,50000))
system.time( order(aa, 1:length(aa)))

[1] 3.67 0.01 3.68 0.00 0.00

system.time( order(aa))

^C
Timing stopped at: 49.33 0.01 49.34 0 0

which is perhaps the simplest work-around :).

There is a simple and very much faster solution if you don't care about 
ordering of ties:

system.time(ord4 <- sort(x, method="quick", index.return = TRUE)$ix)

That is in the help, and I am very surprised you failed to find it.