Suggestions to speed up median() and has.na()

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Suggestions to speed up median() and has.na()

RKoenker
I've recently folded a new version of the Floyd-Rivest quantile  
algorithm
for quantiles into my quantreg package.  So it is easily available for
comparative testing.  On my G5 running last friday's  R-devel, I get:


              Median Only          5 Quantiles
  n          quantile kuantile quantile kuantile qsort
100         0.003    0.003     0.006    0.004 0.002
1000       0.002    0.002     0.002    0.002 0.002
10000     0.005    0.003     0.008    0.003 0.001
1e+05     0.022    0.010     0.035    0.012 0.017
1e+06     0.181    0.117     0.308    0.138 0.200
1e+07     1.853    0.762     3.180    1.003 2.287


# Small timing experiment to compare kuantile and quantile

require(quantreg)
set.seed(1446)

ns <- 10^(2:7)
R <- 10
T <- array(NA,c(R,length(ns),5))
eps <- 20 * .Machine$double.eps
for(j in 1:length(ns)){
     for(i in 1:R){
         y <- rnorm(ns[j])
         T[i,j,1] <- system.time(qy <- quantile(y,.5))[1]
         T[i,j,2] <- system.time(ky <- kuantile(y,.5))[1]
         stopifnot(abs(qy - ky) < eps)
         T[i,j,3] <- system.time(qy <- quantile(y))[1]
         T[i,j,4] <- system.time(ky <- kuantile(y))[1]
         stopifnot(abs(qy - ky) < eps)
         T[i,j,5] <- system.time(sort(y,method="quick"))[1]
         }
     }

Tab <- apply(T,2:3,mean)
dimnames(Tab) <- list(paste(ns),c(rep(c("quantile","kuantile"),
2),"qsort"))

url:    www.econ.uiuc.edu/~roger            Roger Koenker
email    [hidden email]            Department of Economics
vox:     217-333-4558                University of Illinois
fax:       217-244-6678                Champaign, IL 61820

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
Reply | Threaded
Open this post in threaded view
|

Re: Suggestions to speed up median() and has.na()

Brian Ripley
On Windows

> Tab
       quantile kuantile quantile kuantile qsort
100      0.003    0.003    0.000    0.001 0.000
1000     0.000    0.000    0.002    0.000 0.000
10000    0.002    0.004    0.001    0.004 0.000
1e+05    0.008    0.006    0.016    0.010 0.018
1e+06    0.092    0.113    0.137    0.140 0.186
1e+07    0.920    0.685    1.386    0.992 2.274

so the comparison is far less favourable to kuantile.

I remain unconvinced that such small differences are worth the time spend
discussing them.


On Tue, 11 Apr 2006, roger koenker wrote:

> I've recently folded a new version of the Floyd-Rivest quantile
> algorithm
> for quantiles into my quantreg package.  So it is easily available for
> comparative testing.  On my G5 running last friday's  R-devel, I get:
>
>
>              Median Only          5 Quantiles
>  n          quantile kuantile quantile kuantile qsort
> 100         0.003    0.003     0.006    0.004 0.002
> 1000       0.002    0.002     0.002    0.002 0.002
> 10000     0.005    0.003     0.008    0.003 0.001
> 1e+05     0.022    0.010     0.035    0.012 0.017
> 1e+06     0.181    0.117     0.308    0.138 0.200
> 1e+07     1.853    0.762     3.180    1.003 2.287
>
>
> # Small timing experiment to compare kuantile and quantile
>
> require(quantreg)
> set.seed(1446)
>
> ns <- 10^(2:7)
> R <- 10
> T <- array(NA,c(R,length(ns),5))
> eps <- 20 * .Machine$double.eps
> for(j in 1:length(ns)){
>     for(i in 1:R){
>         y <- rnorm(ns[j])
>         T[i,j,1] <- system.time(qy <- quantile(y,.5))[1]
>         T[i,j,2] <- system.time(ky <- kuantile(y,.5))[1]
>         stopifnot(abs(qy - ky) < eps)
>         T[i,j,3] <- system.time(qy <- quantile(y))[1]
>         T[i,j,4] <- system.time(ky <- kuantile(y))[1]
>         stopifnot(abs(qy - ky) < eps)
>         T[i,j,5] <- system.time(sort(y,method="quick"))[1]
>         }
>     }
>
> Tab <- apply(T,2:3,mean)
> dimnames(Tab) <- list(paste(ns),c(rep(c("quantile","kuantile"),
> 2),"qsort"))
>
> url:    www.econ.uiuc.edu/~roger            Roger Koenker
> email    [hidden email]            Department of Economics
> vox:     217-333-4558                University of Illinois
> fax:       217-244-6678                Champaign, IL 61820
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>
>

--
Brian D. Ripley,                  [hidden email]
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

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel