<p><div><div><div><div data-width="100" data-show-faces="false" data-send="true" data-layout="button_count" data-height="21" data-href="https://www.r-bloggers.com/know-your-data-structures/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://blog.haunschmid.name/r-speedup/"> r-bloggers – verenahaunschmid</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Just a few days ago I stated the following on Twitter:</p>
<blockquote data-lang="en" class="twitter-tweet">
<p dir="ltr" lang="en">Just reduced the runtime of an algorithm from 9 hours to 3 min. by using a different data structure… Know you data structures <img alt="🙂" class="wp-smiley" src="https://i0.wp.com/s.w.org/images/core/emoji/2.2.1/72x72/1f642.png?w=456&ssl=1" data-recalc-dims="1"> <a target="_blank" rel="nofollow" href="https://twitter.com/hashtag/rstats?src=hash">#rstats</a></p>
<p>— Verena Haunschmid (@ExpectAPatronum) <a target="_blank" rel="nofollow" href="https://twitter.com/ExpectAPatronum/status/859019899527725057">May 1, 2017</a></p>
</blockquote>
<p></p>
<p>Since my tweet has been liked and shared a lot, I thought I’d backup my claim with a small experiment.</p>
<p>I’ve used my 6 year old Macbook Pro, so if you try this on your computer everything is probably faster!</p>
<h1>Background</h1>
<p>The problem I tried to solve was to implement a genetic algorithm initially programmed <a target="_blank" rel="nofollow" href="https://github.com/rhiever/Data-Analysis-and-Machine-Learning-Projects/blob/master/optimal-road-trip/Computing%20the%20optimal%20road%20trip%20across%20the%20U.S..ipynb">in python by Randy Olson</a>. I’m participating in a <a target="_blank" rel="nofollow" href="http://becomingadatascientist.com/learningclub/forum-29.html">Data Science Learning Club</a> and the current activity was about Genetic Algorithms. The jupyter notebook by Randy was given as an example and we can always choose by ourselves how we want to approach a topic in the learning club. Since I’m currently not doing much in R, I decided it would be a good practice to stay up-to-date.</p>
<p>Here is the <a target="_blank" rel="nofollow" href="https://github.com/expectopatronum/ds-learning-club/blob/master/16-genetic-algorithms/timing_distance_functions.R">complete code for the assignment in my git repo</a>.</p>
<h1>Porting the code</h1>
<p>There will be a lot more detail about the <em>genetic algorithm</em> code in a future blog post. Basically porting it was straight forward. I had to take care of the indices (R starts counting at 1, python at 0) and for me, Python’s indexing is not very intuitive. But I managed to create a running program. Randy’s settings were to use 5000 generations and 100 populations. His python code only took a couple of minutes on my computer.</p>
<h1>Running time</h1>
<p>When I first wanted to run my R code I immediately noticed something was wrong. It needed approximately 7 seconds for one generation, which would result in a complete running time of 9 hours! I stopped the program and tried to investigate what was going on.</p>
<p>I debugged the code and found which part of the function <em>run_genetic_algorithm</em> was the slowest:</p>
<pre>
  for (generation in 1:generations) {
    population_fitness &lt;- list()
    for (i in 1:length(population)) {
      if (!contains(population_fitness, population[[i]])) {
        fit &lt;- compute_fitness_fast(distance_matrix, population[[i]]) # here I had used the method compute_fitness instead of compute_fitness_fast
        agent_fitness &lt;- list(&quot;agent&quot;=population[[i]], &quot;fitness&quot;=unname(fit))
        population_fitness[[length(population_fitness)+1]] &lt;- agent_fitness
      }
    }
</pre>
<p>This part accounted for more than <strong>5 seconds of the 7 seconds</strong> per loop!</p>
<p>At first I thought the loop was the problem because as we all know you should avoid loops in R and use apply, lapply and so on ... </p>
<p>So as a first step I changed the implementation of <em>compute_fitness</em>.</p>
<p>This is the old implementation:</p>
<pre>
compute_fitness &lt;- function(data_store, solution) {
  solution_fitness &lt;- 0.0
  for (index in 2:length(solution)) {
    waypoint1 &lt;- solution[index - 1]
    waypoint2 &lt;- solution[index]
    solution_fitness &lt;- solution_fitness + waypoint_distances(data_store, waypoint1, waypoint2)
  }
  return(solution_fitness)
}
</pre>
<p>This was the first improvement using lapply:</p>
<pre>
compute_fitness_fast &lt;- function(distance_matrix, solution) {
  fitness_list &lt;- lapply(2:length(solution), function(index) {
    waypoint1 &lt;- solution[index - 1]
    waypoint2 &lt;- solution[index]
    waypoint_distances(data_store, waypoint1, waypoint2)
  })
  return(Reduce(&quot;+&quot;, fitness_list))
}
</pre>
<p>This made it slightly better but only cut about half a second from the 5 seconds. Overall this would not reduce the running time by very much. Also notice the use of the method <em>Reduce</em>. While researching on how to improve my code, I also found out about <a target="_blank" rel="nofollow" href="https://stat.ethz.ch/R-manual/R-devel/library/base/html/funprog.html">Common Higher-Order Functions in Functional Programming Languages</a>, which I didn't know existed in R (you might have heard about map/reduce operations before). That's very practical!</p>
<h1>Don't always use data.frames</h1>
<p>Luckily I had the idea that maybe the data.frame where I stored the distances was the problem, since I had to do thousands of lookups. I researched a little and found out that <a target="_blank" rel="nofollow" href="http://stackoverflow.com/a/5159049">matrices have better memory performance</a>. Also the typical structure for storing pairwise distances is a distance matrix... I'm not sure if that's the whole story and what else is going on when I lookup something in a data.frame, but I thought it's worth a try.<br>
I wrote a small script to transform the data.frame into a matrix:</p>
<pre>build_distance_matrix &lt;- function(data_store) {
  all_waypoints &lt;- union(data_store$waypoint1, data_store$waypoint2)
  n &lt;- length(all_waypoints)
  dist_m &lt;- matrix(rep(0, n*n), nrow=n)
  for (i in 1:n) {
    for (j in 1:n) {
      if (i == j) {
        dist_m[i, j] &lt;- 0
      } else if (i &lt; j) {
        dist_ij &lt;- unlist(waypoint_distances(data_store, all_waypoints[i], all_waypoints[j]))
        dist_m[i, j] &lt;- dist_ij
        dist_m[j, i] &lt;- dist_ij
      }
    }
  }
  colnames(dist_m) &lt;- rownames(dist_m) &lt;- all_waypoints
  return(dist_m)
}</pre>
<p>Since I use the city names as column and row names, I can directly use them to access the distance!</p>
<p>And I changed the method <em>compute_fitness_fast</em> to this:</p>
<pre>compute_fitness_fast &lt;- function(distance_matrix, solution) {
  fitness_list &lt;- lapply(2:length(solution), function(index) {
    waypoint1 &lt;- solution[index - 1]
    waypoint2 &lt;- solution[index]
    distance_matrix[waypoint1, waypoint2]
  })
  return(Reduce(&quot;+&quot;, fitness_list))
}</pre>
<p>And yay, I immediately noticed a huge speedup from 5.619 seconds to 0.042 seconds per generation, which is 133 times faster!</p>
<figure class="wp-caption"><a target="_blank" rel="nofollow" href="https://i0.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_dataframe.png"><img sizes="(max-width: 811px) 100vw, 811px" data-image-description="" data-orig-file="https://i0.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_dataframe.png?w=450" data-orig-size="811,307" data-image-title="benchmark_dataframe" data-comments-opened="1" class="wp-image-5759" data-recalc-dims="1" data-attachment-id="5759" data-permalink="http://blog.haunschmid.name/r-speedup/benchmark_dataframe/" alt="Screenshot of a data.frame in R." data-medium-file="http://blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_dataframe-300x114.png" data-large-file="https://i0.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_dataframe.png?w=450" data-image-meta="{" src="https://i0.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_dataframe.png?w=450"></a><br>
<figcaption class="wp-caption-text">My previous data structure, a data.frame of pairwise distances.</figcaption>
</figure>
<figure class="wp-caption"><a target="_blank" rel="nofollow" href="https://i1.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix.png"><img sizes="(max-width: 941px) 100vw, 941px" data-image-description="" data-orig-file="https://i1.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix.png?w=450" data-orig-size="941,336" data-image-title="benchmark_matrix" data-comments-opened="1" class="wp-image-5760" data-recalc-dims="1" data-attachment-id="5760" data-permalink="http://blog.haunschmid.name/r-speedup/benchmark_matrix/" alt="Screenshot of a matrix in R." data-medium-file="http://blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix-300x107.png" data-large-file="https://i1.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix.png?w=450" data-image-meta="{" src="https://i1.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix.png?w=450"></a><br>
<figcaption class="wp-caption-text">My new, faster data structure - a distance matrix.</figcaption>
</figure>
<h1>microbenchmark</h1>
<p>To do the comparison properly, I used the R package <a target="_blank" rel="nofollow" href="https://cran.r-project.org/web/packages/microbenchmark/microbenchmark.pdf">microbenchmark (link to documentation)</a>. You can pass one or more functions/expressions to the <em>microbenchmark</em> method and tell it how often to run the functions for the comparison.</p>
<pre>
res &lt;- microbenchmark(matrix=({
  population_fitness &lt;- list()
  for (agent_genome in population) {
    if (!contains(population_fitness, agent_genome)) {
      fit &lt;- compute_fitness_fast(dist_matrix, agent_genome)
      agent_fitness &lt;- list(&quot;agent&quot;=agent_genome, &quot;fitness&quot;=unname(fit))
      population_fitness[[length(population_fitness)+1]] &lt;- agent_fitness
    }
  }}),
  df=({
    population_fitness &lt;- list()
    for (agent_genome in population) {
      if (!contains(population_fitness, agent_genome)) {
        fit &lt;- compute_fitness(data_store_us, agent_genome)
        agent_fitness &lt;- list(&quot;agent&quot;=agent_genome, &quot;fitness&quot;=unname(fit))
        population_fitness[[length(population_fitness)+1]] &lt;- agent_fitness
      }
    }}),
  times = 100)
</pre>
<p>If you want to plot the results using <em>autoplot</em> it is important to give the functions names (e.g. <em>matrix</em> and <em>df</em>) otherwise it will try to put the whole expressions onto the y axis labels.</p>
<figure class="wp-caption"><a target="_blank" rel="nofollow" href="https://i2.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix_df.png"><img sizes="(max-width: 622px) 100vw, 622px" data-image-description="" data-orig-file="https://i2.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix_df.png?w=450" data-orig-size="622,391" data-image-title="benchmark_matrix_df" data-comments-opened="1" class="wp-image-5703" data-recalc-dims="1" data-attachment-id="5703" data-permalink="http://blog.haunschmid.name/r-speedup/benchmark_matrix_df/" alt="" data-medium-file="http://blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix_df-300x189.png" data-large-file="https://i2.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix_df.png?w=450" data-image-meta="{" src="https://i2.wp.com/blog.haunschmid.name/wp-content/uploads/2017/05/benchmark_matrix_df.png?w=450"></a><br>
<figcaption class="wp-caption-text">Pretty clear results!</figcaption>
</figure>
<p>And as you can see, just by replacing the data.frame by the more suitable matrix, this important part of my algorithm became a lot faster!</p>
<p><a target="_blank" rel="nofollow" href="http://www.gettinggeneticsdone.com/2015/01/microbenchmark-package-r-compare-runtime-r-expressions.html">>> Using the microbenchmark package to compare the execution time of R expressions | gettinggeneticsdone.com</a></p>
<h1>Takeaway from this post</h1>
<p>What I learned from this problem and maybe also you, is that you should never just use the data structure that is given. I simply read the csv file that was stored by the Jupyter notebook (it seems to be very efficient in Python) and used the first data structure that seemed to fit. In this case it would have made sense to think about what the underlying structure of the data is. There is one number for each pair of cities, which makes a matrix a real good fit. The name <em>distance matrix</em> already suggests how it should be stored <img alt="🙂" class="wp-smiley" src="https://i0.wp.com/s.w.org/images/core/emoji/2.2.1/72x72/1f642.png?w=456&ssl=1" data-recalc-dims="1"></p>
<p>I'd also like to know more about the underlying reason why there is such a huge distance. If you have any more resources, I'd like to read/hear about it!</p>
<p>The post <a target="_blank" rel="nofollow" href="http://blog.haunschmid.name/r-speedup/">Know your data structures!</a> appeared first on <a target="_blank" rel="nofollow" href="http://blog.haunschmid.name/">verenahaunschmid</a>.</p>
<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="http://blog.haunschmid.name/r-speedup/"> r-bloggers – verenahaunschmid</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a title="The R Project for Statistical Computing" rel="nofollow" href="https://www.r-project.org/">R</a> news and <a title="R tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/tutorial">tutorials</a> on topics such as: <a title="Data science" rel="nofollow" href="https://www.r-bloggers.com/search/data%20science">Data science</a>, <a title="Big Data" rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data">Big Data, <a title="R jobs" rel="nofollow" href="https://www.r-users.com/">R jobs</a>, visualization (<a title="ggplot and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2">ggplot2</a>, <a title="Boxplots using lattice and ggplot2 tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/boxplot">Boxplots</a>, <a title="Maps and gis" rel="nofollow" href="https://www.r-bloggers.com/search/map">maps</a>, <a title="Animation in R" rel="nofollow" href="https://www.r-bloggers.com/search/animation">animation</a>), programming (<a title="RStudio IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/RStudio">RStudio</a>, <a title="Sweave and literate programming" rel="nofollow" href="https://www.r-bloggers.com/search/sweave">Sweave</a>, <a title="LaTeX in R" rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX">LaTeX</a>, <a title="SQL and databases" rel="nofollow" href="https://www.r-bloggers.com/search/SQL">SQL</a>, <a title="Eclipse IDE for R" rel="nofollow" href="https://www.r-bloggers.com/search/eclipse">Eclipse</a>, <a title="git and github, Version Control System" rel="nofollow" href="https://www.r-bloggers.com/search/git">git</a>, <a title="Large data in R using Hadoop" rel="nofollow" href="https://www.r-bloggers.com/search/hadoop">hadoop</a>, <a title="Web Scraping of google, facebook, yahoo, twitter and more using R" rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping">Web Scraping</a>) statistics (<a title="Regressions and ANOVA analysis tutorials" rel="nofollow" href="https://www.r-bloggers.com/search/regression">regression</a>, <a title="principal component analysis tutorial" rel="nofollow" href="https://www.r-bloggers.com/search/PCA">PCA</a>, <a title="Time series" rel="nofollow" href="https://www.r-bloggers.com/search/time+series">time series</a>, <a title="finance trading" rel="nofollow" href="https://www.r-bloggers.com/search/trading">trading</a>) and more...
<img height="1" alt="" width="1" src="http://feeds.feedburner.com/~r/RBloggers/~4/gw1H9CVJhFY"></a></div>