R optimization: midpoint

In several algorithm (e.g. binary search) you need to find the mid-point among two indexes. In practice you have to compute the integer average of the two indexes. In R there are several ways of performing the computation, three that may easily come to your mind are:

(x+y) %/% 2
as.integer( (x+y)/2 )
trunc((x+y)/2)

Which one is the most efficient?

To find out I run a small experiment:

I collected a few samples of the time required to perform a fairly large number of mid-point calculations using this script:

x= as.integer(rnorm(10000000,10,2))
y= as.integer(rnorm(10000000,11,2))
time.asint = c()
time.trunc = c()
time.div = c()
for(i in 1:100){
  time.div = c(time.div,system.time( (x+y) %/% 2L )["user.self"])
  time.trunc = c(time.trunc,system.time( trunc((x+y)/2) )["user.self"])
  time.asint = c(time.asint,system.time( as.integer((x+y)/2) )["user.self"])
}

I run the script in my Mac Book Pro, on R version 3.0.2.

The results can be easily appreciated using a boxplot (warning: y axis does not start a 0):

MidPointR

An the winner is: as.integer(). Computing a normal division and then converting to integer takes 5% less time than performing an integer division (%/%), which in its turn takes 17% less time than performing a division and then truncating the decimal part.

Annunci

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...