From rkoenker at uiuc.edu  Tue Apr 11 14:51:39 2006
From: rkoenker at uiuc.edu (roger koenker)
Date: Tue, 11 Apr 2006 07:51:39 -0500
Subject: [Rd]  Suggestions to speed up median() and has.na()
Message-ID: <625D9846-00B6-4DA8-8440-A185FBC80B7E@uiuc.edu>

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    rkoenker at uiuc.edu            Department of Economics
vox:     217-333-4558                University of Illinois
fax:       217-244-6678                Champaign, IL 61820



[Rd] Suggestions to speed up median() and has.na()
roger koenker