Message-ID: <Pine.A41.4.44.0306080905570.61872-100000@homer03.u.washington.edu>
Date: 2003-06-08T16:12:13Z
From: Thomas Lumley
Subject: Ordering long vectors
In-Reply-To: <Pine.LNX.4.44.0306071803540.26490-100000@tal.stat.umu.se>
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 :).
-thomas