Waste less time on Facebook — follow Brilliant.
×

Conway's Game of Life - Optimization of Python Program

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]

Note by Raj Magesh
3 years, 1 month ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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:

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

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:

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))

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:

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}

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 · 3 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...