[R] Benchmarking R, why sort() is so slow?

Thomas Lumley tlumley at u.washington.edu
Fri Apr 27 17:23:28 CEST 2001


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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._



More information about the R-help mailing list