Speed up recursion in R 600-fold with Rcpp

September 12, 2011
By

(This article was first published on Revolutions, and kindly contributed to R-bloggers)

Rcpp package co-author Dirk Eddelbuettel provides another case study in speeding up R code by rewriting repeatedly-called R code as inline C++ functions, using the classic Fibonacci recursion algorithm as an example.

The speed gains here are impressive -- over 600x compared to native recursive R code -- but you could also improve performance by using a more efficient, non-recursive algorithm in R directly. But sometimes recoding can be both easier and safer, as Dirk explains:

Improved algorithms for well-understood problems are surely one way to accelerate solutions. But there are (many ?) times when we do not have the luxury of being able to think through to a new and improved approach. Or worse, such an approach may even introduce new errors or inaccurracies if we get it wrong on a first try. With Rcpp, we are able to the express the problem as written in its original statement: a simple recursion. The gain relative to a slow R implementation is noteworthy---and could of course be improved further if we really needed to by relying on better algorithms like memoization. But for day to day tasks, I gladly take speedups of (up to) a few hundred times thanks to Rcpp without having to do hard algorithmic work.

If you'd like to learn more techniques for using Rcpp for improving the performance of R code, Dirk is giving two live one-day workshops on Rcpp on September 24 in New York, and on October 8 in San Francisco.

Thinking Inside the Box: Faster (recursive) function calls: Another quick Rcpp case study 

To leave a comment for the author, please follow the link and comment on his blog: Revolutions.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.