Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

It was suggested to me that I should post this Stack Overflow post over here.

Here is the code as it stands right now:

import numpy as np
from matplotlib import pyplot as plt
from matplotlib import animation
from random import randint

arraySize = 50
Z = np.array([[randint(0, 1) for x in range(arraySize)] for y in range(arraySize)])


def computeNeighbours(Z):
    rows, cols = len(Z), len(Z[0])
    N = np.zeros(np.shape(Z))

    for x in range(rows):
        for y in range(cols):
            Q = [q for q in [x-1, x, x+1] if ((q >= 0) and (q < cols))]
            R = [r for r in [y-1, y, y+1] if ((r >= 0) and (r < rows))]
            S = [Z[q][r] for q in Q for r in R if (q, r) != (x, y)]
            N[x][y] = sum(S)

    return N

def iterate(Z):
    Zprime = Z.copy()
    rows, cols = len(Zprime), len(Zprime[0])
    N = computeNeighbours(Zprime)

    for x in range(rows):
        for y in range(cols):
            if Zprime[x][y] == 1:
                if (N[x][y] < 2) or (N[x][y] > 3):
                    Zprime[x][y] = 0
            else:
                if (N[x][y] == 3):
                    Zprime[x][y] = 1

    return Zprime

fig = plt.figure()

Zs = [Z]
ims = []

for i in range(0, 100):
    im = plt.imshow(Zs[len(Zs)-1], interpolation = 'nearest', cmap='binary')
    ims.append([im])
    Zs.append(iterate(Zs[len(Zs)-1]))

ani = animation.ArtistAnimation(fig, ims, interval=250, blit=True)
plt.show()

I am interested in knowing what sequence of optimizations one would perform for this sort of an application, so that I can get a handle on how to use NumPy's power for my current project, which is simply a (perhaps) three dimensional, cellular automaton with many rules.

share|improve this question
add comment

1 Answer 1

up vote 11 down vote accepted

I'll just be cheeky and post a slightly modified version of my SO answer here.

So first things first, you want to get rid of the loops. They are slow to execute.

The first loop:

for x in range(rows):
        for y in range(cols):
            if Z[x][y] == 1:
                if (N[x][y] < 2) or (N[x][y] > 3):
                    Z[x][y] = 0
            else:
                if (N[x][y] == 3):
                    Z[x][y] = 1

could be replaced by:

set_zero_idxs = (Z==1) & ((N<2) | (N>3))
set_one_idxs = (Z!=1) & (N==3)
Z[set_zero_idxs] = 0
Z[set_one_idxs] = 1

Here you are generating boolean arrays that indicate which values satisfy your criteria and then you are setting those values to either 0 or 1.

Benchmarking this we see a significant improvement in speed (x 180):

# new version without loop
In [49]: %timeit no_loop(z,n)
1000 loops, best of 3: 177 us per loop

# original version with loop 
In [50]: %timeit loop(z,n)
10 loops, best of 3: 31.2 ms per loop

The second major loop:

for x in range(rows):
        for y in range(cols):
            Q = [q for q in [x-1, x, x+1] if ((q >= 0) and (q < cols))]
            R = [r for r in [y-1, y, y+1] if ((r >= 0) and (r < rows))]
            S = [Z[q][r] for q in Q for r in R if (q, r) != (x, y)]
            N[x][y] = sum(S)

could be replaced by:

N = np.roll(Z,1,axis=1) + np.roll(Z,-1,axis=1) + np.roll(Z,1,axis=0) + np.roll(Z,-1,axis=0)

[Note: this is actually wrong for the game of life, as the code should check for diagonal neighbours as well. This is simply a refactoring of the original for loop construct.]

Here there is an implicit assumption that the array does not have bounds and that x[-1] is next to x[0]. If this is a problem, you could add a buffer of zeros around your array with:

shape = Z.shape
new_shape = (shape[0]+2,shape[1]+2)
# b_z is a new array which will be our buffer
b_z = np.zeros(new_shape)

# set the middle of the array equal to the original `Z`
b_z[1:-1,1:-1] = Z

# do our rolls on the buffered array so that we don't have boundary isssues
b_n = np.roll(b_z,1,axis=1) + np.roll(b_z,-1,axis=1) + np.roll(b_z,1,axis=0) + np.roll(b_z,-1,axis=0)

# write back the part of the array that is of interest to us
N = b_n[1:-1,1:-1]

and for a benchmark:

# original function with loops
In [4]: %timeit computeNeighbours(z)
10 loops, best of 3: 140 ms per loop 

# new function without a buffer
In [5]: %timeit noloop_computeNeighbours(z)
10000 loops, best of 3: 133 us per loop

# new function with a buffer to remove boundary counts
In [6]: %timeit noloop_with_buffer_computeNeighbours(z)
10000 loops, best of 3: 170 us per loop

So just a small improvement of a factor of x 1052. Hooray for Numpy!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.