R help - Aug 2008 - x[order(x)] vs sort(x)?

Hi

I have a question (which may be an obvious one). It is about an idiom which I
have seen quite often:

o <- order(x); <- x[o]

vs. the alternative

x <- sort(x)

I am just wondering as to the rationale behind the order/reindex idiom vs
sorting. Especially as there seems to be a marked performance difference
(especially for integer vectors):
> x <- trunc(runif(1E6, 1, 100))
> system.time(y <- x[order(x)])
   user  system elapsed
   1.19    0.01    1.21
> system.time(y <- sort(x))
   user  system elapsed
   0.22    0.00    0.22

I suspect that the propensity for the order/reindex idiom may be related to
memory or space performance then, rather than time? Can anyone confirm if this
is the case?

Cheers
Rory



***********************************************************************************
The Royal Bank of Scotland plc. Registered in Scotland No 90312. Registered
Office: 36 St Andrew Square, Edinburgh EH2 2YB.
Authorised and regulated by the Financial Services Authority 

This e-mail message is confidential and for use by the=2...{{dropped:22}}

On Thu, 21 Aug 2008, Rory.WINSTON at rbs.com wrote:
> Hi
>
> I have a question (which may be an obvious one). It is about an idiom 
> which I have seen quite often:
>
> o <- order(x); <- x[o]
>
> vs. the alternative
>
> x <- sort(x)
>
> I am just wondering as to the rationale behind the order/reindex idiom vs
sorting. Especially as there seems to be a marked performance difference
(especially for integer vectors):
>
>> x <- trunc(runif(1E6, 1, 100))
Those are doubles, BTW.
>> system.time(y <- x[order(x)])
>   user  system elapsed
>   1.19    0.01    1.21
>> system.time(y <- sort(x))
>   user  system elapsed
>   0.22    0.00    0.22
>
> I suspect that the propensity for the order/reindex idiom may be related 
> to memory or space performance then, rather than time? Can anyone 
> confirm if this is the case?
You don't give any examples of where you have seen the idiom, so leave us 
to guess.

order() is usually used when it is needed for other objects: even for 
sort() this applies to the names.  And x[o] is used to preserve classes, 
for example: look at the code of sort.default.  And sort.list has a method 
for radix sorting ideally suited to your example.

There are faster options for sort, too.

On my system
> x <- trunc(runif(1E6, 1, 100))
> system.time(y <- x[order(x)])
    user  system elapsed
   1.128   0.010   1.471
> system.time(y <- sort(x))
    user  system elapsed
   0.138   0.005   0.259
> system.time(y <- sort.int(x, method="quick"))
    user  system elapsed
   0.073   0.000   0.132
> x <- as.integer(x)
> system.time(y <- x[sort.list(x, method="radix")])
    user  system elapsed
   0.033   0.001   0.053
> names(x) <- 1:1e6
> system.time(y <- sort(x))
    user  system elapsed
   0.715   0.023   1.475
> system.time(y <- sort.int(x, method="quick"))
    user  system elapsed
   1.519   0.015   3.077
> system.time(y <- x[sort.list(x, method="radix")])
    user  system elapsed
   0.138   0.000   0.287



-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595