Counting Neighbors (Why scipy.signal.convolve2D so fast?)

Here is my Python implementation of counting neighbours of Game of Life with radius as parameter.

def neighbors_count(n2d_array, radii=1):
    assert n2d_array.ndim == 2
    row_len, col_len = n2d_array.shape
    nbrs_count = np.zeros_like(n2d_array)
    for row_idx, row_val in enumerate(n2d_array):
         for col_idx, col_val in enumerate(row_val):
             start_row = 0 if (row_idx-radii)  row_len else (row_idx+radii+1)
             start_col = 0 if (col_idx-radii)  row_len else (col_idx+radii+1)
             neighbor = 0
             for block_row_idx in np.arange(start_row, end_row):
                 for block_col_idx in np.arange(start_col, end_col):
                     neighbor += n2d_array[block_row_idx, block_col_idx]
             nbrs_count[row_idx, col_idx] = neighbor - n2d_array[row_idx, col_idx]
     return nbrs_count

I found out that my implementation is very slow compared to scipy.signal.convolve2d:

def neighbors_count2(n2d_array, radii=1):
    from scipy.signal import convolve2d
    diameter = 2 * radii + 1
    n2d_array = n2d_array.astype(bool)
    nbrs_count = convolve2d(n2d_array, np.ones((diameter, diameter)),
                            mode='same', boundary='fill') - n2d_array
    return nbrs_count

Here is %timeit result in my computer:

%timeit -n 10 neighbors_count(np.random.randint(2, size=(100,100)))
10 loops, best of 3: 232 ms per loop

%timeit -n 10 neighbors_count2(np.random.randint(2, size=(100,100)))
10 loops, best of 3: 963 µs per loop

How to improve/vectorize my code so it can run faster than scipy.signal.convolve2d?

You can change your algorithmic approach to improve your speed.

Currently:

• look at every cell

• lookup every neighbor-cell

• write the number of neighbors

My proposition:
You start with a zero-ed nbrs_count array and look at every cell. If it's occupied, increase the nbrs_count of all neighboring cells (you will get a huge speedup if the array is mostly empty).

To prevent all your conditional statements, you can simply use a try: ... except: block, as suggested by @JoeWallis

Here is an implementation using my propositions:

import numpy as np

def neighbors_count(n2d_array, radii=1):
assert n2d_array.ndim == 2

nbrs_count = np.zeros_like(n2d_array)

# array of adjacents cells
adjacents = []
for i in range(-radii, radii + 1):
for j in range(-radii, radii + 1):
if j != 0 or i != 0:
adjacents.append((i,j))

for (row_idx, col_idx), value in np.ndenumerate(n2d_array):
if value:
for i, j in adjacents:
try:
if row_idx + i >= 0 and col_idx + j >= 0:
# because a negative index doesn't fail
nbrs_count[row_idx + i, col_idx + j] += 1
except IndexError:
# We are outside the array
pass

return nbrs_count


This solution is about 5 times faster than the original code (which is still way slower than scipy)

StackExchange Code Review Q#93267, answer score: 3