Propagating true entries along axis in an array

Question

I have to perform the operation below many times. Using numpy functions instead of loops I usually get a very good performance but I have not been able to replicate this for higher dimensional arrays. Any suggestion or alternative would be most welcome:

I have a boolean array and I would like to propagate the true indeces to the next 2 positions for example:

If this 1 dimensional array (A) is:

import numpy as np

# Number of positions to propagate the array
propagation = 2

# Original array
A = np.array([False, True, False, False, False, True, False, False, False, False, False, True, False])

I can create an "empty" array and then find the indices, propagate them, and then flatten argwhere and then flatten it:

B = np.zeros(A.shape, dtype=bool)

# Compute the indeces of the True values and make the two next to it True as well
idcs_true = np.argwhere(A) + np.arange(propagation + 1)
idcs_true = idcs_true.flatten()
idcs_true = idcs_true[idcs_true < A.size] # in case the error propagation gives a great
B[idcs_true] = True

# Array
print(f'Original array     A = {A}')
print(f'New array (2 true) B = {B}')

which gives:

Original array     A = [False  True False False False  True False False False False False  True
 False]
New array (2 true) B = [False  True  True  True False  True  True  True False False False  True
  True]

However, this becomes much more complex and fails if for example:

AA = np.array([[False, True, False, False, False, True, False, False, False, False, False, True, False],
               [False, True, False, False, False, True, False, False, False, False, False, True, False]])

Thanks for any advice.

Do you need this only for 2D arrays? Is numba an option (I think the algorithm could be nicely parallelized)? — Andrej Kesely
– Andrej Kesely, Commented Apr 12, 2024 at 21:09
Hi @AndrejKesely, thank you for your comment. For the current case yes 2D (m, n) boolean array is enough. I would rather start with just numpy to avoid the extra dependencies. — Delosari
– Delosari, Commented Apr 12, 2024 at 21:48

mozway · Accepted Answer · 2024-04-13 06:03:11Z

You can achieve this with a convolution (numpy.convolve):

propagation = 2

A = np.array([False, True, False, False, False, True, False, False, False, False, False, True, False])

# generate kernel
k = np.r_[np.zeros(propagation, dtype=bool),
          np.ones(propagation+1, dtype=bool)]
# array([False, False,  True,  True,  True])

# convolve to propagate the True
out = np.convolve(A, k, mode='same')

Output:

array([False,  True,  True,  True, False,  True,  True,  True, False,
       False, False,  True,  True])

For a 2D array, with scipy.signal.convolve2d and a 2D kernel:

from scipy.signal import convolve2d

AA = np.array([[False, True, False, False, False, True, False, False, False, False, False, True, False],
               [False, True, False, False, False, True, False, False, False, False, False, True, False]])

# generate 2D kernel
k = np.r_[np.zeros(propagation),
          np.ones(propagation+1)][None]
# array([[0, 0, 1, 1, 1]])

out = convolve2d(AA, k, mode='same').astype(bool)

Output:

array([[False,  True,  True,  True, False,  True,  True,  True, False,
        False, False,  True,  True],
       [False,  True,  True,  True, False,  True,  True,  True, False,
        False, False,  True,  True]])

Naitzirch · Accepted Answer · 2024-04-12 22:05:05Z

You could maybe wrap your current code in a function, then feed this along with your 2-D AA array to the np.apply_along_axis function.

import numpy as np

# Number of positions to propagate the array
propagation = 2

# Original array
AA = np.array([[False, True, False, False, False, True, False, False, False, False, False, True, False],
             [False, True, False, False, False, True, False, False, False, False, False, True, False]])

def prop_func(A):
    B = np.zeros(A.shape, dtype=bool)

    # Compute the indices of the True values and make the two next to it True as well
    idcs_true = np.argwhere(A) + np.arange(propagation + 1)
    idcs_true = idcs_true.flatten()
    idcs_true = idcs_true[idcs_true < A.size] # in case the error propagation gives a great
    B[idcs_true] = True
    return B

# Apply prop_func along the rows (axis=1)
BB = np.apply_along_axis(prop_func, 1, AA)

# Array
print(f'Original array     AA = {AA}')
print(f'New array (2 true) BB = {BB}')

Original array     AA = 
[[False  True False False False  True False False False False False  True
  False]
 [False  True False False False  True False False False False False  True
  False]]
New array (2 true) BB = 
[[False  True  True  True False  True  True  True False False False  True
   True]
 [False  True  True  True False  True  True  True False False False  True
   True]]

Thank you very much for the reply, sorry I can only choose one.

Andrej Kesely · Accepted Answer · 2024-04-13 00:22:11Z

I just leave here numba version so you can compare the speed against the proposed numpy solution:

import numba
import numpy as np


@numba.njit(parallel=True)
def propagate_true_numba(arr, n=2):
    out = np.zeros_like(arr, dtype="uint8")

    for i in numba.prange(arr.shape[0]):
        prop = 0
        for j in range(arr.shape[1]):
            if arr[i, j] == 1:
                prop = n
                out[i, j] = 1
            elif prop:
                prop -= 1
                out[i, j] = 1

    return out

Benchmark:

import numba
import numpy as np
import perfplot


@numba.njit(parallel=True)
def propagate_true_numba(arr, n=2):
    out = np.zeros_like(arr, dtype="uint8")

    for i in numba.prange(arr.shape[0]):
        prop = 0
        for j in range(arr.shape[1]):
            if arr[i, j] == 1:
                prop = n
                out[i, j] = 1
            elif prop:
                prop -= 1
                out[i, j] = 1

    return out


def _prop_func(A, propagation):
    B = np.zeros(A.shape, dtype=bool)

    # Compute the indices of the True values and make the two next to it True as well
    idcs_true = np.argwhere(A) + np.arange(propagation + 1)
    idcs_true = idcs_true.flatten()
    idcs_true = idcs_true[
        idcs_true < A.size
    ]  # in case the error propagation gives a great
    B[idcs_true] = True
    return B


def propagate_true_numpy(arr, n=2):
    return np.apply_along_axis(_prop_func, 1, arr, n)


AA = np.array([[False, True, False, False, False, True, False, False, False, False, False, True, False],
             [False, True, False, False, False, True, False, False, False, False, False, True, False]])

x = propagate_true_numba(AA, 2)
y = propagate_true_numpy(AA, 2)
assert np.allclose(x, y)

np.random.seed(0)

perfplot.show(
    setup=lambda n: np.random.randint(0, 2, size=(n, n), dtype="uint8"),
    kernels=[
        lambda arr: propagate_true_numpy(arr, 2),
        lambda arr: propagate_true_numba(arr, 2),
    ],
    labels=["numpy", "numba"],
    n_range=[10, 25, 50, 100, 250, 500, 1000, 2500, 5000],
    xlabel="N * N",
    logx=True,
    logy=True,
    equality_check=np.allclose,
)

Creates on my AMD 5700x this graph:

Collectives™ on Stack Overflow

Propagating true entries along axis in an array

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related