Temukan Jarak ke Nol Terdekat di NumPy Array

Katakanlah saya memiliki array NumPy:

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

Pada setiap indeks, saya ingin mencari jarak ke nilai nol terdekat. Jika posisinya nol maka kembalikan nol sebagai jarak. Setelah itu, kami hanya tertarik pada jarak ke nol terdekat yaitu di sebelah kanan posisi saat ini. Pendekatan super naif akan seperti:

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

Dan hasilnya adalah:

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

Saya memperhatikan pola hitung mundur / penurunan dalam output di antara nol. Jadi, saya mungkin bisa menggunakan lokasi nol (yaitu, zero_indices = np.argwhere(x == 0).flatten())

Apa cara tercepat untuk mendapatkan output yang diinginkan dalam waktu linier?

Pendekatan # 1: Searchsorted untuk penyelamatan linear-waktu secara vektor (sebelum numba datang)!

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

Pendekatan # 2: Lainnya dengan beberapa 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))

Atau, langkah terakhir cumsumdapat diganti dengan repeatfungsi -

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

Pendekatan # 3: Lain-lain dengan hanya sebagian besar 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

Anda bisa bekerja dari sisi lain. Simpan penghitung pada berapa banyak digit bukan nol yang telah lewat dan tetapkan ke elemen dalam array. Jika Anda melihat 0, atur ulang penghitung ke 0

Sunting: jika tidak ada nol di sebelah kanan, maka Anda perlu memeriksa lagi

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)

Anda dapat menggunakan perbedaan antara indeks dari setiap posisi dan jumlah kumulatif dari posisi nol untuk menentukan jarak ke nol sebelumnya. Ini bisa dilakukan maju dan mundur. Minimum antara jarak maju dan mundur ke nol sebelumnya (atau berikutnya) adalah yang terdekat:

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)

hasil:

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]

Kasus khusus di mana tidak ada nol hadir di tepi luar:

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]

juga bekerja tanpa nol sama sekali

[EDIT]  solusi non-numpy ...

jika Anda mencari solusi O (N) yang tidak membutuhkan numpy, Anda dapat menerapkan strategi ini menggunakan fungsi akumulasi dari itertools:

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)

keluaran:

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]

Jika Anda tidak ingin menggunakan pustaka apa pun, Anda dapat mengakumulasi jarak secara manual dalam satu lingkaran:

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)

keluaran:

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]

Intuisi pertama saya adalah menggunakan slicing. Jika x dapat berupa daftar normal alih-alih array numpy, maka Anda dapat menggunakannya

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

jika numpy diperlukan maka Anda bisa menggunakannya

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

tetapi ini kurang efisien karena Anda menemukan semua nol lokasi di sebelah kanan nilai dan kemudian menarik keluar hanya yang pertama. Hampir pasti cara yang lebih baik untuk melakukan ini di numpy.

Sunting: Saya minta maaf, saya salah paham. Ini akan memberi Anda jarak ke nol terdekat - mungkin di kiri atau kanan. Tetapi Anda dapat menggunakan d_rightsebagai hasil antara. Ini tidak mencakup kasus tepi tidak memiliki nol di sebelah kanan sekalipun.

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])