More efficient way of suming over a matrix in numpy/regular python

Question

Good day, for my studies I created a cellular automato in 2 Dimension. The program is already running but I still try to optimize it. The piece of code bellow sums up all 8 neighbor cells of the central cell in a 2D array. After that the next cell gets defined as a function of the sum. Is there a faster way than 2 for-loops?

Before I even had 4 for loops for the summation, but it was 2 time slower than it's now...

n = len(mat1)
m = len(mat1[0])
mat2 = np.zeros((n,m))
sumN = 0
start = time.time()
for i in range(1,n-1):  
    for j in range(1,m-1):
        sumN = mat1[i-1,j-1] + mat1[i-1,j] + mat1[i-1,j+1] + mat1[i,j-1] +mat1[i,j+1] + mat1[i+1,j] + mat1[i+1,j+1]+ mat1[i+1,j-1]
        if str(sumN) in B and mat1[i,j] == 0:
            mat2[i,j] = 1
        elif str(sumN) in S and mat1[i,j] == 1:
            mat2[i,j] = 1
        sumN = 0
end = time.time()
print end - start

Thanks to xnx, I included the roll over the matrix instead of looping over all elements. After that I created a boolean 2D numpy array which I use to initialize the next generation.

sumN = sum(np.roll(np.roll(mat1, i, 0), j, 1)
for i in (-1, 0, 1) for j in (-1, 0, 1)
  if (i != 0 or j != 0)).flatten()

mat1 = mat1.flatten()

b = np.array(map(lambda x,l: ((int(x) == 0) and (str(int(l)) in B)) 
   or ((int(x) == 1) and (str(int(l)) in S)), mat1,sumN)).reshape(n,m)                           
mat2 = np.zeros((n,m))                                                      
mat2[b] = 1                                                         
mat2 = mat2.reshape(n,m)

I also used the sum function of numpy over the 3x3 matrix inside the loop, but it was even slower... — Noveel
– Noveel, Commented Jan 28, 2016 at 13:52
can you simply use convolution? For example, scipy.signal.convolve2d.with the shape of your kernel? docs.scipy.org/doc/scipy-0.16.0/reference/generated/… — otterb
– otterb, Commented Jan 28, 2016 at 14:54
What is the point of the str(sumN) in B and str(sumN) in S calls? Why are you computing a value then trying to see if the string representation of a number is in B or S? What are B and S? Lists? Strings? This will help so I can craft an answer for you. — rayryeng
– rayryeng, Commented Jan 28, 2016 at 16:31
B(birth),S(survive) are strings, for example in game of life B would be just 3 and S 23 ... The user initialize the rule with B=... and S = ... en.wikipedia.org/wiki/Life-like_cellular_automaton — Noveel
– Noveel, Commented Jan 29, 2016 at 15:17

xnx · Accepted Answer · 2016-01-28 14:01:04Z

2

A nice way to do this is given in this blog article:

nbrs_count = sum(np.roll(np.roll(mat1, i, 0), j, 1)
                 for i in (-1, 0, 1) for j in (-1, 0, 1)
                 if (i != 0 or j != 0))

It works because numpy.roll(a, shift, axis) shifts the elements along a given axis, axis, a specified number of places, shift with wrapping, so each of the 8 cells can be visited in turn if you iterate over rows i=-1,0,1 and columns j=-1,0,1 but take care not to count the centre cell itself.

edited Jan 28, 2016 at 14:01

answered Jan 28, 2016 at 13:54

xnx

25.7k11 gold badges75 silver badges117 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Noveel Over a year ago

This rely speeds it up! Thanks for sharing!

CoMartel · Accepted Answer · 2016-01-28 15:03:34Z

Not sure if this is faster (you should check it with your data set), but what you try to do seems close to image processing.

Scikit image is a pretty good module for this, and there is a very good chance to be much faster than your solution, as a lot of features are implemented in C/Fortran.

from skimage.morphology import square
import skimage.filters.rank as rank
import numpy as np

sumN=rank.sum(mat1,square(3)) # sum of each pixels in a 3 pixel-sided square

# compare with B and S :
n,m =np.shape(mat1)
sumN=np.flatten(sumN) # vectorize your array to be faster
mat1=np.flatten(sumN)
mat2=np.zeros_like(mat1)
for i in range(len(mat1): # only looping on 1 variable is faster
    if str(sumN[i]) in B and mat1[i] == 0:
        mat2[i] = 1
    elif str(sumN[i]) in S and mat1[i] == 1:
        mat2[i] = 1
mat1=mat1.reshape(n,m) # go back to the previous shape
mat2=mat2.reshape(n,m)

Collectives™ on Stack Overflow

More efficient way of suming over a matrix in numpy/regular python

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related