Finden Sie die Entfernung zum nächsten Nullpunkt im NumPy-Array

Angenommen, ich habe ein NumPy-Array:

x = np.array([0, 1, 2, 0, 4, 5, 6, 7, 0, 0])

Bei jedem Index möchte ich den Abstand zum nächsten Nullwert ermitteln. Wenn die Position selbst eine Null ist, geben Sie als Abstand Null zurück. Danach interessieren uns nur noch Entfernungen zur nächsten Null rechts von der aktuellen Position. Der super naive Ansatz wäre so etwas wie:

out = np.full(x.shape[0], x.shape[0]-1)
for i in range(x.shape[0]):
    j = 0
    while i + j < x.shape[0]:
        if x[i+j] == 0:
            break
        j += 1
    out[i] = j

Und die Ausgabe wäre:

array([0, 2, 1, 0, 4, 3, 2, 1, 0, 0])

Ich bemerke ein Countdown- / Dekrementmuster in der Ausgabe zwischen den Nullen. Ich könnte also in der Lage sein, die Positionen der Nullen zu verwenden (dh zero_indices = np.argwhere(x == 0).flatten())

Was ist der schnellste Weg, um die gewünschte Ausgabe in linearer Zeit zu erhalten?

Ansatz Nr. 1: Searchsorted Zur vektorisierten Rettung der linearen Zeit (bevor Numba-Typen hereinkommen)!

mask_z = x==0
idx_z = np.flatnonzero(mask_z)
idx_nz = np.flatnonzero(~mask_z)

# Cover for the case when there's no 0 left to the right
# (for same results as with posted loop-based solution)
if x[-1]!=0:
    idx_z = np.r_[idx_z,len(x)]

out = np.zeros(len(x), dtype=int)
idx = np.searchsorted(idx_z, idx_nz)
out[~mask_z] = idx_z[idx] - idx_nz

Ansatz Nr. 2: Ein anderer mit einigen cumsum-

mask_z = x==0
idx_z = np.flatnonzero(mask_z)

# Cover for the case when there's no 0 left to the right
if x[-1]!=0:
    idx_z = np.r_[idx_z,len(x)]

out = idx_z[np.r_[False,mask_z[:-1]].cumsum()] - np.arange(len(x))

Alternativ könnte der letzte Schritt von cumsumdurch repeatFunktionalität ersetzt werden -

r = np.r_[idx_z[0]+1,np.diff(idx_z)]
out = np.repeat(idx_z,r)[:len(x)] - np.arange(len(x))

Ansatz Nr. 3: Ein anderer mit meist nur cumsum-

mask_z = x==0
idx_z = np.flatnonzero(mask_z)

pp = np.full(len(x), -1)
pp[idx_z[:-1]] = np.diff(idx_z) - 1
if idx_z[0]==0:
    pp[0] = idx_z[1]
else:
    pp[0] = idx_z[0]
out = pp.cumsum()

# Handle boundary case and assigns 0s at original 0s places
out[idx_z[-1]:] = np.arange(len(x)-idx_z[-1],0,-1)
out[mask_z] = 0

Sie könnten von der anderen Seite arbeiten. Behalten Sie einen Zähler für die Anzahl der Ziffern ungleich Null bei und weisen Sie ihn dem Element im Array zu. Wenn Sie 0 sehen, setzen Sie den Zähler auf 0 zurück

Bearbeiten: Wenn rechts keine Null steht, benötigen Sie eine weitere Prüfung

x = np.array([0, 1, 2, 0, 4, 5, 6, 7, 0, 0])
out = x 
count = 0 
hasZero = False 
for i in range(x.shape[0]-1,-1,-1):
    if out[i] != 0:
        if not hasZero: 
            out[i] = x.shape[0]-1
        else:
            count += 1
            out[i] = count
    else:
        hasZero = True
        count = 0
print(out)

Sie können die Differenz zwischen den Indizes jeder Position und dem kumulierten Maximum von Nullpositionen verwenden, um den Abstand zur vorhergehenden Null zu bestimmen. Dies kann vorwärts und rückwärts erfolgen. Der Mindestabstand zwischen Vorwärts- und Rückwärtsabstand zur vorhergehenden (oder nächsten) Null ist der nächste:

import numpy as np

indices  = np.arange(x.size)
zeroes   = x==0
forward  = indices - np.maximum.accumulate(indices*zeroes)  # forward distance
forward[np.cumsum(zeroes)==0] = x.size-1                    # handle absence of zero from edge
forward  = forward * (x!=0)                                 # set zero positions to zero                

zeroes   = zeroes[::-1]
backward = indices - np.maximum.accumulate(indices*zeroes) # backward distance
backward[np.cumsum(zeroes)==0] = x.size-1                  # handle absence of zero from edge
backward = backward[::-1] * (x!=0)                         # set zero positions to zero

distZero = np.minimum(forward,backward) # closest distance (minimum)

Ergebnisse:

distZero
# [0, 1, 1, 0, 1, 2, 2, 1, 0, 0]

forward
# [0, 1, 2, 0, 1, 2, 3, 4, 0, 0]

backward
# [0, 2, 1, 0, 4, 3, 2, 1, 0, 0]

Sonderfall, bei dem an den Außenkanten keine Nullen vorhanden sind:

x = np.array([3, 1, 2, 0, 4, 5, 6, 0,8,8])

forward:  [9 9 9 0 1 2 3 0 1 2]
backward: [3 2 1 0 3 2 1 0 9 9]
distZero: [3 2 1 0 1 2 1 0 1 2]

funktioniert auch ohne Nullen

[EDIT]  nicht numpy Lösungen ...

Wenn Sie nach einer O (N) -Lösung suchen, für die kein Numpy erforderlich ist, können Sie diese Strategie mithilfe der Akkumulationsfunktion von itertools anwenden:

x = [0, 1, 2, 0, 4, 5, 6, 7, 0, 0]

from itertools import accumulate

maxDist  = len(x) - 1
zeroes   = [maxDist*(v!=0) for v in x]
forward  = [*accumulate(zeroes,lambda d,v:min(maxDist,(d+1)*(v!=0)))]
backward = accumulate(zeroes[::-1],lambda d,v:min(maxDist,(d+1)*(v!=0)))
backward = [*backward][::-1]
distZero = [min(f,b) for f,b in zip(forward,backward)]                      

print("x",x)
print("f",forward)
print("b",backward)
print("d",distZero)

Ausgabe:

x [0, 1, 2, 0, 4, 5, 6, 7, 0, 0]
f [0, 1, 2, 0, 1, 2, 3, 4, 0, 0]
b [0, 2, 1, 0, 4, 3, 2, 1, 0, 0]
d [0, 1, 1, 0, 1, 2, 2, 1, 0, 0]

Wenn Sie keine Bibliothek verwenden möchten, können Sie die Entfernungen manuell in einer Schleife akkumulieren:

x = [0, 1, 2, 0, 4, 5, 6, 7, 0, 0]
forward,backward = [],[]
fDist = bDist = maxDist = len(x)-1
for f,b in zip(x,reversed(x)):
    fDist = min(maxDist,(fDist+1)*(f!=0))
    forward.append(fDist)
    bDist = min(maxDist,(bDist+1)*(b!=0))
    backward.append(bDist)
backward = backward[::-1]
distZero = [min(f,b) for f,b in zip(forward,backward)]

print("x",x)
print("f",forward)
print("b",backward)
print("d",distZero)

Ausgabe:

x [0, 1, 2, 0, 4, 5, 6, 7, 0, 0]
f [0, 1, 2, 0, 1, 2, 3, 4, 0, 0]
b [0, 2, 1, 0, 4, 3, 2, 1, 0, 0]
d [0, 1, 1, 0, 1, 2, 2, 1, 0, 0]

Meine erste Intuition wäre das Schneiden. Wenn x eine normale Liste anstelle eines numpy-Arrays sein kann, können Sie verwenden

 out = [x[i:].index(0) for i,_ in enumerate(x)]

Wenn numpy notwendig ist, können Sie verwenden

 out = [np.where(x[i:]==0)[0][0] for i,_ in enumerate(x)]

Dies ist jedoch weniger effizient, da Sie alle Nullstellen rechts vom Wert finden und dann nur die erste herausziehen. Fast definitiv ein besserer Weg, dies in Numpy zu tun.

Edit: Es tut mir leid, ich habe falsch verstanden. Dies gibt Ihnen den Abstand zu den nächsten Nullen - kann es links oder rechts sein. Sie können aber d_rightals Zwischenergebnis verwenden. Dies gilt jedoch nicht für den Randfall, dass rechts keine Null steht.

import numpy as np

x = np.array([0, 1, 2, 0, 4, 5, 6, 7, 0, 0])

# Get the distance to the closest zero from the left:
zeros = x == 0
zero_locations = np.argwhere(x == 0).flatten()
zero_distances = np.diff(np.insert(zero_locations, 0, 0))

temp = x.copy()
temp[~zeros] = 1
temp[zeros] = -(zero_distances-1)
d_left = np.cumsum(temp) - 1

# Get the distance to the closest zero from the right:
zeros = x[::-1] == 0
zero_locations = np.argwhere(x[::-1] == 0).flatten()
zero_distances = np.diff(np.insert(zero_locations, 0, 0))

temp = x.copy()
temp[~zeros] = 1
temp[zeros] = -(zero_distances-1)
d_right = np.cumsum(temp) - 1
d_right = d_right[::-1]

# Get the smallest distance from both sides:
smallest_distances = np.min(np.stack([d_left, d_right]), axis=0)
# np.array([0, 1, 1, 0, 1, 2, 2, 1, 0, 0])