Conway's Game of Life - Optimization of Python Program - Raj Magesh

Hey Guys,

Recently, someone shared a few problems about Conway's Game of Life, which I tried to simulate in Python. I'm still relatively new to Python and have no clue how I could optimize the program.

Could you please suggest improvements, with your reasoning included?

If you have tried simulating this, could you also post your code?

Thanks a lot!

Code:

#---------------------------------------------------------------------------
# Name:        Conway's Game of Life - A Simulation
# Author:      G Raj Magesh
# Created:     29-01-2014
# Copyright:   (c) G Raj Magesh 2014
#
# m = rows
# n = columns
# l = list of 1s and 0s from left to right
# c = counter
#---------------------------------------------------------------------------
def ReturnList(m, n, l):
    newlist = []
    for x in range(0, m*n):
        c = 0
        if x > n-1:
            if l[x - n] == 1:
                c += 1
        if x < m*n-n:
            if l[x + n] == 1:
                c += 1
        if x%n != 0:
            if l[x-1] == 1:
                c += 1
        if (x + 1) % n != 0:
            if l[x + 1] == 1:
                c += 1
        if x > n - 1 and x%n != 0:
            if l[x - n - 1] == 1:
                c += 1
        if x > n - 1 and (x + 1) % n != 0:
            if l[x - n + 1] == 1:
                c += 1
        if x < m*n - n and x%n != 0:
            if l[x + n - 1] == 1:
                c += 1
        if x < m*n - n and (x + 1) % n != 0:
            if l[x + n + 1] == 1:
                c += 1
        if l[x] == 1:
            if c == 2 or c == 3:
                newlist.append(1)
            else:
                newlist.append(0)
        else:
            if c == 3:
                newlist.append(1)
            else:
                newlist.append(0)
    return newlist

def PrintBoard(m, n, l):
    c = 0
    for x in l:
        if c%n == 0:
            print "[" + str(x),
        elif (c+1)%n == 0:
            print str(x) + "]"
        else:
            print str(x),
        c += 1

def IterateXTimes(m, n, l, X):
    c = 0
    while c <= X:
        print "------- Iteration " + str(c) + " -------"
        PrintBoard(m, n, l)
        l = ReturnList(m, n, l)
        c += 1

IterateXTimes(4, 3, [1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0], 5)

Output:

------- Iteration 0 -------
[1 0 0]
[0 0 1]
[0 1 0]
[0 1 0]
------- Iteration 1 -------
[0 0 0]
[0 1 0]
[0 1 1]
[0 0 0]
------- Iteration 2 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 3 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 4 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]
------- Iteration 5 -------
[0 0 0]
[0 1 1]
[0 1 1]
[0 0 0]

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

time python ./game_of_life.py ------- Iteration 0 ------- [1 0 0] [0 0 1] [0 1 0] [0 1 0] ------- Iteration 1 ------- [0 0 0] [0 1 0] [0 1 1] [0 0 0] ------- Iteration 2 ------- [0 0 0] [0 1 1] [0 1 1] [0 0 0] ------- Iteration 3 ------- [0 0 0] [0 1 1] [0 1 1] [0 0 0] ------- Iteration 4 ------- [0 0 0] [0 1 1] [0 1 1] [0 0 0] ------- Iteration 5 ------- [0 0 0] [0 1 1] [0 1 1] [0 0 0] real 0m0.023s user 0m0.012s sys 0m0.008s

def IterateXTimes(m, n, l, X): timers = defaultdict(float) c = 0 timers['last'] = time.time() while c <= X: timers['main_loop_overhead'] += time.time() - timers['last'] timers['last'] = time.time() print "------- Iteration " + str(c) + " -------" timers['iteration_print'] += time.time() - timers['last'] timers['last'] = time.time() PrintBoard(m, n, l) timers['print_board'] += time.time() - timers['last'] timers['last'] = time.time() l = ReturnList(m, n, l) timers['return_list'] += time.time() - timers['last'] timers['last'] = time.time() c += 1 pprint.pprint(dict(timers))

def PrintBoard(m, n, l): board = [l[x*n:x*n+n] # slice the board up into a matrix for x in xrange(m)] print board {'iteration_print': 9.393692016601562e-05, 'main_loop_overhead': 8.106231689453125e-06, 'print_board': 9.703636169433594e-05, 'return_list': 0.0001289844512939453}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

I've been hoping someone else would step in and help out, but I guess I can get it started since I spend a decent amount of time optimizing stuff here at Brilliant.

The first rule of optimization is to be able to measure the impact of changes that you make.

If you are on a linux or mac machine you should be able to use the time command from the shell when running the program to get a rough estimate of the amount of time your program will take to run overall:

After you have the overall number, it's usually good to start digging down to see what exact parts take the most time (especially when the number is relatively small such as in this case, where you'd get different numbers depending on what else your computer is doing in the background, etc).

Modifying the code in these ways will give a tiny bit more insight:

Add to top:

import time
import pprint
from collections import defaultdict

replace IterateXTimes:

Which then will add this to the output:

{'iteration_print': 8.058547973632812e-05,
 'main_loop_overhead': 5.9604644775390625e-06,
 'print_board': 0.00019812583923339844,
 'return_list': 0.00012993812561035156}

So already, we notice that surprisingly, printing the board takes longer that computing the next level.

We can get a pretty good speedup on that function by converting the list to a 2d array and then just printing it out directly to reduce the amount of int-> string conversions as well as separate print functions:

As with most things, I'm pretty confident that if it's worth it for you to do (optimization for the sake of optimization isn't usually a good idea, it should be because you will be able to work more efficiently or use the program in a different and better way), there are more optimizations that could be had, but I'll let you try to take it from here. One suggestion would be to see if you can figure out how to get your algorithm to work with a matrix so that you can eliminate the conversion at print time (and it may or may not also allow you to speed up the ReturnList function).

Another thing to note is that it is sorta hard to see "real" timings when you deal with small data-sets, to be more scientific, you should probably increase the board size to something closer to what you'll actually run it on and then also increase the number of iterations (in the main loop and perhaps also perform several runs of the entire program and average times across the different runs (or at least ignore the really high or really low results)).

And finally: if you are going to be running this with a main loop iteration of thousands, printing the board over and over again to the standard output could get costly and it may be better to skip printing all of them unless you need to inspect each and every one of them afterwards, or append to a file (either straight from python or by telling the command line to send the output to a file: python ./game_of_life.py > ./game_of_life_results.txt)

Sam Solomon Staff - 7 years, 4 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$