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

[Peter Dalgaard BSA]

"Philippe Grosjean" <phgrosje at ulb.ac.be> writes:

> Hello everybody,
> 
> I am making a modified version of "Stephan Steinhaus' benchmark test for
> number crunching, v. 2, (see
> http://www.scinetificweb.com/ncrunch/ncrunch.pdf for the original version),
> comparing several functions of some math/stat software. R is not performing
> bad at all... except for the sorting of a 1,100,000 random vector (test #3)
> which is the worst of all (see cell F3 in the following table). I simply
> used the sort() function. Does anybody has an explanation for that?

The internal algorithm is a shellsort, which is supposedly of
complexity O(n^1.25) and has decent worst-case behaviour. Other
algorithms like quicksort have typical performance of O(n log n) but
extreme cases of O(n^2).

For large vectors the O(n^.25/log(n)) relative complexity is going to
make a difference, although the observed differences seem larger.

There are very likely better choices of sort algorithm...

-- 
   O__  ---- Peter Dalgaard             Blegdamsvej 3  
  c/ /'_ --- Dept. of Biostatistics     2200 Cph. N   
 (*) \(*) -- University of Copenhagen   Denmark      Ph: (+45) 35327918
~~~~~~~~~~ - (p.dalgaard at biostat.ku.dk)             FAX: (+45) 35327907
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._