Much more efficient bubble sort in R using the Rcpp and inline packages

Recently I wrote a blogpost showing the implementation of a simple bubble sort algorithm in pure R code. The downside of that implementation was that is was awfully slow. And by slow, I mean really slow, as in “a 100 element vector takes 7 seconds to sort”-slow. One of the major opportunities for a speed is to start using a compiled language. I chose to use C++ as this is really easy to integrate into R using the Rcpp package. In addition to the Rcpp package I use the inline package which allows one to use C++ code and R code in a seamless fashion. The following code creates an R function bubble_sort_cpp:

Quite amazing how easy it is to integrate R code and C++ code. inline compiles and links the C++ code on-the-fly, creating an R function that delivers the functionality. Of course the most important question is now how fast this is. I use the microbenchmark package to run the bubble sort I implemented in pure R (here), the bubble sort implemented in C++ (see above), and the standard R sorting algorithm:

These results speak for itself, the C++ version is more than 1300 times faster when looking at the median speed, even faster than the built-in sort function. These differences will only get more pronounced when the size of the vector grows.

Tagged with: , , ,
Posted in R stuff
2 Comments » for Much more efficient bubble sort in R using the Rcpp and inline packages
  1. Paul Hiemstra says:

    I recently got a tip form Hadley Wickham through e-mail that pre-computing vec_in.size() once, and not every pass, makes a big difference in performance (x2). This is the new code:

    • Arun says:

      base:::sort by default uses shell sort which is O(n^(4/3)). So, the difference may not be apparent on a vector of size 100 when comparing Rcpp‘s bubble sort to base‘s. Since your vector is all positive and the range is < 1e5, you can also try out bases’s counting sort (improperly named as radix sort) as follows: system.time(x[sort.list(x, method="radix")]) (not to edit this post, but for trying it out yourself). Also, base’s sort methods internally account for NAs which hits performance.

1 Pings/Trackbacks for "Much more efficient bubble sort in R using the Rcpp and inline packages"
  1. […] hands, and implemented the bubble sort algorithm that I have already posted about several times (R, C++). The main argument for Julia is it’s speed. It claims speeds comparable to that of a […]

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax

*