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 [EMAIL PROTECTED] Department of Economics
vox: 217-333-4558 University of Illinois
fax: 217-244-6678 Champaign, IL 61820
______________________________________________
R-devel@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
