<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/conways-game-of-life-in-r-or-on-the-importance-of-vectorizing-your-r-code/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="http://www.win-vector.com/blog/2018/10/conways-game-of-life-in-r-or-on-the-importance-of-vectorizing-your-r-code/"> R – Win-Vector Blog</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p><a rel="nofollow" href="https://www.r-project.org/" target="_blank">R</a> is an interpreted programming language with vectorized data structures. This means a single R command can ask for very many arithmetic operations to be performed. This also means R computation can be fast. We will show an example of this using <a rel="nofollow" href="https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" target="_blank">Conway’s Game of Life</a>.</p>
<p><span></span></p>
<p>
<p>Conway’s Game of Life is one of the most interesting examples of cellular automata. It is traditionally simulated on a rectangular grid (like a chessboard) and each cell is considered either live or dead. The rules of evolution are simple: the next life grid is computed as follows:</p>
<ul>
<li>To compute the state of a cell on the next grid sum the number of live cells in the eight neighboring cells on the current grid.</li>
<li>If this sum is 3 or if the current cell is live <em>and</em> the sum is 2 or 3, then the cell in the next grid will be live.</li>
</ul>
<p>This rule can be implemented as scalar code in R:</p>
<pre>
# d is a matrix of logical values
life_step_scalar &lt;- function(d) {
  nrow &lt;- dim(d)[[1]]
  ncol &lt;- dim(d)[[2]]
  dnext &lt;- matrix(data = FALSE, nrow = nrow, ncol = ncol)
  for(i in seq_len(nrow)) {
    for(j in seq_len(ncol)) {
      pop &lt;- 0
      if(i>1) {
        if(j>1) {
          pop &lt;- pop + d[i-1, j-1]
        }
        pop &lt;- pop + d[i-1, j]
        if(j&lt;ncol) {
          pop &lt;- pop + d[i-1, j+1]
        }
      }
      if(j>1) {
        pop &lt;- pop + d[i, j-1]
      }
      if(j&lt;ncol) {
        pop &lt;- pop + d[i, j+1]
      }
      if(i&lt;nrow) {
        if(j>1) {
          pop &lt;- pop + d[i+1, j-1]
        }
        pop &lt;- pop + d[i+1, j]
        if(j&lt;ncol) {
          pop &lt;- pop + d[i+1, j+1]
        }
      }
      dnext[i,j] &lt;- (pop==3) || (d[i,j] &amp;&amp; (pop>=2) &amp;&amp; (pop&lt;=3))
    }
  }
  dnext
}
</pre>
<p>We could probably speed the above code up by a factor of 2 to 4 by eliminating the if-statements which requires writing 9 versions of the for-loops (depending if the index is in the right-boundary, interior, or left-boundary of its range). However, as we are about to see- this is not worth the effort.</p>
<p>A much faster implementation is the vector implementation found <a rel="nofollow" href="https://github.com/WinVector/FastBaseR/blob/master/R/ConwayLife.R" target="_blank">here</a>.</p>
<pre>
life_step &lt;- function(d) {
  # form the neighboring sums
  nrow &lt;- dim(d)[[1]]
  ncol &lt;- dim(d)[[2]]
  d_eu &lt;- rbind(d[-1, , drop = FALSE], 0)
  d_ed &lt;- rbind(0, d[-nrow, , drop = FALSE])
  d_le &lt;- cbind(d[ , -1, drop = FALSE], 0)
  d_re &lt;- cbind(0, d[ , -ncol, drop = FALSE])
  d_lu &lt;- cbind(d_eu[ , -1, drop = FALSE], 0)
  d_ru &lt;- cbind(0, d_eu[ , -ncol, drop = FALSE])
  d_ld &lt;- cbind(d_ed[ , -1, drop = FALSE], 0)
  d_rd &lt;- cbind(0, d_ed[ , -ncol, drop = FALSE])
  pop &lt;- d_eu + d_ed + d_le + d_re + d_lu + d_ru + d_ld + d_rd
  d &lt;- (pop==3) | (d &amp; (pop>=2) &amp; (pop&lt;=3))
  d
}
</pre>
<p>The way this code works is: it builds 8 copies of the life-table, one shifting each neighboring cell into the current cell-position. With these 8 new matrices the entire life forward evolution rule is computed vectorized over all cells using the expression “<code>(pop==3) | (d &amp; (pop>=2) &amp; (pop&lt;=3))</code>“. Notice the vectorized code is actually shorter: we handle the edge-cases by zero-padding.</p>
<p>The performance difference is substantial:</p>
<p><img border="0" src="https://i0.wp.com/www.win-vector.com/blog/wp-content/uploads/2018/10/present-1.png?resize=660%2C471" alt="Present 1" width="450" title="present-1.png" data-recalc-dims="1"></p>
<p>The vectorized code is about 10 times faster on average (details can be found <a rel="nofollow" href="https://github.com/WinVector/FastBaseR/blob/master/extras/ConwayLife/Timing.md" target="_blank">here</a>).</p>
<p>A simulation of this type produces figures such as the following:</p>
<p><a rel="nofollow" href="https://github.com/WinVector/FastBaseR/blob/master/extras/ConwayLife/life_example.md" target="_blank"><img border="0" src="https://i2.wp.com/github.com/WinVector/FastBaseR/raw/master/extras/ConwayLife/glider_gun2.gif?resize=500%2C500&ssl=1" alt="Glider gun2" width="450" title="glider_gun2.gif" data-recalc-dims="1"></a></p>
<p>Of course if you are serious about Conway’s Game of Life you would use specialized software (even in-browser JavaScript), and specialized algorithms (such as <a rel="nofollow" href="https://en.wikipedia.org/wiki/Hashlife" target="_blank">HashLife</a>).</p>
<p>One objection is: the vectorized code uses more memory. To that I give the following famous quote:</p>
<blockquote>
<p>
The biggest difference between time and space is that you can’t reuse time. </p>
<p>-Merrick Furst
</p>
</blockquote>
<p>And that is our (toy) example of vectorizing code. Techniques such as these are why very fast and powerful code can in fact be written in R.</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://www.win-vector.com/blog/2018/10/conways-game-of-life-in-r-or-on-the-importance-of-vectorizing-your-r-code/"> R – Win-Vector Blog</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 rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/S5DBB6KkhgA" height="1"></a></div>