alexa

How would I check if each cell of an array has neighbors of a specified value quickly in numpy python ?

How would I check if each cell of an array has neighbors of a specified value quickly in numpy python ?

If you just want to use numpy, my way is to find out the neighbors of all true values in the original array, the calculation method is to judge whether the Chebyshev distance (L-infinite distance) between the position of elements in the array and the position of true values is 1, then merge them with logical or operation:

 >>> ar = np.array([[0,0,0,1,0],
... [0,0,0,0,0],
... [0,1,0,0,0],
... [0,0,0,1,0],
... [0,0,0,0,0]], bool)
>>> row, col = ar.nonzero()
>>> rows, cols = np.indices(ar.shape)
>>> np.logical_or.reduce([np.maximum(np.abs(rows - i), np.abs(cols - j)) == 1 for i, j in zip(row, col)])
array([[False, False,  True, False,  True],
       [ True,  True,  True,  True,  True],
       [ True, False,  True,  True,  True],
       [ True,  True,  True, False,  True],
       [False, False,  True,  True,  True]]) 

By broadcasting, you can also avoid the list comprehension:

 >>> rows, cols = np.indices(ar.shape, sparse=True)  # Setting to sparse does not affect the calculation.
>>> i = np.abs(rows[None] - row[:, None, None])
>>> j = np.abs(cols[None] - col[:, None, None])
>>> np.logical_or.reduce(np.maximum(i, j) == 1)
array([[False, False,  True, False,  True],
       [ True,  True,  True,  True,  True],
       [ True, False,  True,  True,  True],
       [ True,  True,  True, False,  True],
       [False, False,  True,  True,  True]]) 

To make the code look shorter, I used None instead of np.newaxis, you can use the latter for readability.

After testing, even with the help of broadcasting, it is slower than the second answer of @d.b , but it is not too bad:

 >>> def loop_reduce(ar):
...     row, col = ar.nonzero()
...     rows, cols = np.indices(ar.shape)
...     return np.logical_or.reduce([np.maximum(np.abs(rows - i), np.abs(cols - j)) == 1 for i, j in zip(row, col)])
...
>>> def broadcast_reduce(ar):
...     row, col = ar.nonzero()
...     rows, cols = np.indices(ar.shape, sparse=True)
...     i = np.abs(rows[None] - row[:, None, None])
...     j = np.abs(cols[None] - col[:, None, None])
...     return np.logical_or.reduce(np.maximum(i, j) == 1)
...
>>> def max_filter(ar):
...     ans = maximum_filter(ar, size=(3, 3))
...     ans[ar] = False
...     return ans
...
>>> timeit(lambda: loop_reduce(ar), number=10000)
0.3127206000208389
>>> timeit(lambda: broadcast_reduce(ar), number=10000)
0.15011020001838915
>>> timeit(lambda: max_filter(ar), number=10000)
0.12893440001062118 

At least this can be a way for you to solve similar problems in the future :-)


243 0
7

Write a Comments


* Be the first to Make Comment

GoodFirms Badge
GoodFirms Badge

Fix Your Meeting With Our SEO Consultants in India To Grow Your Business Online

Facebook
Twitter
LinkedIn
Instagram
Whatsapp
Call Now
Quick Inquiry