Оптимизация поиска по краю

Question

У меня есть Pandas фрейм данных, в котором я храню двоичные данные в столбце из ~ 360 000 записей. Я ищу способ найти изменения между 0 -> 1 и 1 -> 0 более эффективным способом.

В настоящее время я просматриваю его и проверяю определенные условия c путем оценки каждый индекс, который может быть достаточно описательным для чтения, но, поскольку функциональность используется несколько раз, на самом деле является узким местом более крупного скрипта. Последний индекс не отмечен, но это не критично.

for i in range(0, len(df.Binary) - 1):
    if df.Binarywindow[i] == 0 and df.Binarywindow[i+1] == 1:
        startedge.append(i)
    elif df.Binarywindow[i] == 1 and df.Binarywindow[i+1] == 0:
        endedge.append(i)

Не могли бы вы помочь мне его переписать?

Answer 1

Упомянутый вами метод действительно даст довольно медленные результаты для больших наборов данных из-за того, как методы append () взаимодействуют с памятью. По сути, вы перезаписываете одну и ту же часть памяти ~ 360 000 раз, расширяя ее одной записью. Вы можете значительно ускорить это, преобразовав в массивы numpy и используя одну операцию для поиска краев. Я написал минимальный пример для демонстрации со случайным набором двоичных данных.

binaries = np.random.randint(0,2,200000)
Binary = pd.DataFrame(binaries)

t1 = time.time()

startedge, endedge = pd.DataFrame([]), pd.DataFrame([])
for i in range(0, len(Binary) - 1):
    if Binary[0][i] == 0 and Binary[0][i+1] == 1:
        startedge.append([i])
    elif Binary[0][i] == 1 and Binary[0][i+1] == 0:
        endedge.append([i])

t2 = time.time()
print(f"Looping through took {t2-t1} seconds")

# Numpy based method, including conversion of the dataframe
t1 = time.time()
binary_array = np.array(Binary[0])

startedges = search_sequence_numpy(binary_array, np.array([0,1]))
stopedges = search_sequence_numpy(binary_array, np.array([1,0]))

t2 = time.time()
print(f"Converting to a numpy array and looping through required {t2-t1} seconds")

Вывод:

Looping through took 56.22933220863342 seconds
Converting to a numpy array and looping through required 0.029932022094726562  seconds

Для функции поиска последовательности я использовал код из этого ответа Поиск последовательности в массиве NumPy

def search_sequence_numpy(arr,seq):
""" Find sequence in an array using NumPy only.

Parameters
----------    
arr    : input 1D array
seq    : input 1D array

Output
------    
Output : 1D Array of indices in the input array that satisfy the 
matching of input sequence in the input array.
In case of no match, an empty list is returned.
"""

# Store sizes of input array and sequence
Na, Nseq = arr.size, seq.size

# Range of sequence
r_seq = np.arange(Nseq)

# Create a 2D array of sliding indices across the entire length of input array.
# Match up with the input sequence & get the matching starting indices.
M = (arr[np.arange(Na-Nseq+1)[:,None] + r_seq] == seq).all(1)

# Get the range of those indices as final output
if M.any() >0:
    return np.where(np.convolve(M,np.ones((Nseq),dtype=int))>0)[0]
else:
    return []         # No match found