Timing the Same Algorithm in R, Python, and C++
This article is originally published at http://www.win-vector.com/blog
This means I can time the exact same algorithm implemented nearly identically in each of these three languages. So I can extract some comparative “apples to apples” timings. Please read on for a summary of the results.
The algorithm in question is the general dynamic programming solution to the “minimum cost partition into intervals” problem. As coded in
C++ it uses one-time allocation of large tables and then
for-loops and index chasing to fill in the dynamic programming table solution. The
C++ code is given here.
I then directly transliterated (or line-for line translated) this code into
R (code here) and
Python (code here). Both of these implementations are very direct translations of the
C++ solution, so they are possibly not what somebody starting in
Python would design. So really we are coding in an an imperative
C style in
Python. To emphasize the shallowness of the port I deliberately left the semi-colons from the
C++ in the
R port. The
Python can be taken to be equally “un-Pythonic” (for example, we are using
for loops and not list comprehensions).
|problem||solution language||time in seconds|
|500 point partition into intervals dynamic program||R||21|
|500 point partition into intervals dynamic program||C++ (from R via Rcpp)||0.088|
|500 point partition into intervals dynamic program||Python||39|
Notice for this example
C++ is 240 times faster than
R is almost twice as fast as
Python is optimized for the type of index-chasing this dynamic programming solution depends on. So we also took a look at a simpler problem: computing the PRESS statistic, which is easy to vectorize (a preferred writing efficient code in
Python). When we compare all three languages on this problem we see the following.
|problem||solution method||time in seconds|
|3,000,000 point PRESS statistic calculation||R scalar code||3.4|
|3,000,000 point PRESS statistic calculation||Rcpp scalar code||0.26|
|3,000,000 point PRESS statistic calculation||R vectorized code||0.35|
|3,000,000 point PRESS statistic calculation||Python vectorized (
R scalar solution (which is too direct a translation from
R, but a stepping stone to the
R vectorized solution as we discuss here). We see: vectorized
Python is now about 1.6 times faster than the vectorized
R and even 1.2 times faster than the
C++ (probably not due to
Rcpp, but instead driven by my choice of container class in the
Obviously different code (and per-language tuning and optimization) will give different results. But the above is consistent with our general experience with
C++ in production.
Python are in fact much slower than
C++ for direct scalar manipulation (single values, indexes, and pointers). However,
Python are effective glue languages that can be fast when they are orchestrating operations over higher level abstractions (vectors, databases, data frames, and Spark).
Please visit source website for post related comments.