NumPy 배열이 있다고 가정 해 봅시다.
x = np.array([0, 1, 2, 0, 4, 5, 6, 7, 0, 0])각 인덱스에서 가장 가까운 0 값까지의 거리를 찾고 싶습니다. 위치가 0 자체 인 경우 거리로 0을 반환합니다. 그 후, 현재 위치의 오른쪽에있는 가장 가까운 0까지의 거리에만 관심이 있습니다. 슈퍼 순진한 접근 방식은 다음과 같습니다.
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
결과는 다음과 같습니다.
array([0, 2, 1, 0, 4, 3, 2, 1, 0, 0])0 사이의 출력에서 카운트 다운 / 감소 패턴을 발견했습니다. 그래서 나는이 0의 위치를 사용 할 수 있습니다 (즉, zero_indices = np.argwhere(x == 0).flatten())
선형 출력으로 원하는 출력을 얻는 가장 빠른 방법은 무엇입니까?
답변
접근법 # 1 : Searchsorted 벡터화 된 방식으로 선형 시간을 구하기 위해 (난바 사람들이 들어 오기 전에)!
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
접근법 # 2 : 또 다른 하나 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))
또는 마지막 단계는 기능 cumsum으로 대체 될 수 있습니다.repeat
r = np.r_[idx_z[0]+1,np.diff(idx_z)]
out = np.repeat(idx_z,r)[:len(x)] - np.arange(len(x))
접근법 # 3 : 주로 다른 것 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
답변
다른 쪽에서 일할 수 있습니다. 0이 아닌 숫자가 몇 개나 통과했는지 카운터를 유지하고 배열의 요소에 지정하십시오. 0이 표시되면 카운터를 0으로 재설정하십시오.
편집 : 오른쪽에 0이 없으면 다른 검사가 필요합니다.
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)
답변
각 위치의 인덱스와 누적 최대 영점 위치의 차이를 사용하여 앞의 0까지의 거리를 결정할 수 있습니다. 이 작업은 앞뒤로 수행 할 수 있습니다. 앞 (또는 다음) 0까지의 앞뒤 거리 사이의 최소값이 가장 가깝습니다.
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)
결과 :
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]
바깥 쪽 가장자리에 0이없는 특수한 경우 :
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]
전혀 0없이 작동합니다.
[편집] 숫자가 아닌 솔루션 …
numpy가 필요없는 O (N) 솔루션을 찾고 있다면 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)
산출:
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]
라이브러리를 사용하지 않으려면 루프에서 수동으로 거리를 누적 할 수 있습니다.
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)
산출:
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]
답변
첫 번째 직감은 슬라이싱을 사용하는 것입니다. x가 numpy 배열 대신 일반 목록이 될 수 있다면
out = [x[i:].index(0) for i,_ in enumerate(x)]numpy가 필요한 경우 사용할 수 있습니다
out = [np.where(x[i:]==0)[0][0] for i,_ in enumerate(x)]그러나 값 오른쪽의 모든 0 위치를 찾은 다음 첫 번째 위치 만 꺼내기 때문에 효율성이 떨어집니다. numpy에서 이것을 수행하는 거의 확실히 더 좋은 방법입니다.
답변
편집 : 죄송합니다, 오해합니다. 이것은 가장 가까운 0까지의 거리를 제공합니다-왼쪽 또는 오른쪽에있을 수 있습니다. 그러나 d_right중간 결과로 사용할 수 있습니다. 그러나 오른쪽에 0이없는 경우에는 적용되지 않습니다.
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])
답변
