Message-ID: <Pine.A41.4.33.0104270814010.36572-100000@homer40.u.washington.edu>
Date: 2001-04-27T15:23:28Z
From: Thomas Lumley
Subject: Benchmarking R, why sort() is so slow?
In-Reply-To: <MABBLJDICACNFOLGIHJOIECDCDAA.phgrosje@ulb.ac.be>
On Fri, 27 Apr 2001, Philippe Grosjean wrote:
> I suspect it should be a question of algorithm choice. May be sort() is
> important enough, including for large datasets, to place some improvement in
> the "to do" list for a further version...?
>
Actually, I'm not convinced on the speed issue. Shellsort works very well
for vectors of lengths that R can reasonably handle. Using a million
record dataset in R you really can't get much done in the 20seconds that a
really good sorting routine might save you.
Heapsort might be worth trying -- it has good worst-case behaviour and is
about half as fast as the typical case of quicksort. Merge sort might
also be nice because it's stable: it leaves ties in the order it found
them, but it needs extra space. Still, I don't think it's a high
optimisation priority.
-thomas
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !) To: r-help-request at stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._