From ripley at stats.ox.ac.uk  Tue Apr 11 15:04:31 2006
From: ripley at stats.ox.ac.uk (Prof Brian Ripley)
Date: Tue, 11 Apr 2006 14:04:31 +0100 (BST)
Subject: [Rd] Suggestions to speed up median() and has.na()
In-Reply-To: <625D9846-00B6-4DA8-8440-A185FBC80B7E@uiuc.edu>
References: <625D9846-00B6-4DA8-8440-A185FBC80B7E@uiuc.edu>
Message-ID: <Pine.LNX.4.64.0604111400030.5402@gannet.stats.ox.ac.uk>

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

-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
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



[Rd] Suggestions to speed up median() and has.na()
Prof Brian Ripley