Numpy: найдите индексы краев маски

Aiven спросил: 28 апреля 2018 в 08:34 в: python

Я пытаюсь найти недостатки скрытых сегментов. Например:

mask = [1, 0, 0, 1, 1, 1, 0, 0]
segments = [(0, 0), (3, 5)]

Текущее решение выглядит так (и это медленное very, потому что моя маска содержит миллионы чисел):

segments = []
start = 0
for i in range(len(mask) - 1):
    e1 = mask[i]
    e2 = mask[i + 1]
    if e1 == 0 and e2 == 1:
        start = i + 1
    elif e1 == 1 and e2 == 0:
        segments.append((start, i))

Есть ли способ сделать это эффективно с помощью numpy?

Единственное, что мне удалось сделать в google, - numpy.ma.notmasked_edges, но это не похоже что мне нужно.

2 ответа

Есть решение
Divakar ответил: 28 апреля 2018 в 08:54

Вот один из подходов -

def start_stop(a, trigger_val):
    # "Enclose" mask with sentients to catch shifts later on
    mask = np.r_[False,np.equal(a, trigger_val),False]    # Get the shifting indices
    idx = np.flatnonzero(mask[1:] != mask[:-1])    # Get the start and end indices with slicing along the shifting ones
    return zip(idx[::2], idx[1::2]-1)

Пример прогона -

In [216]: mask = [1, 0, 0, 1, 1, 1, 0, 0]In [217]: start_stop(mask, trigger_val=1)
Out[217]: [(0, 0), (3, 5)]

Используйте его для получения ребер для 0s -

In [218]: start_stop(mask, trigger_val=0)
Out[218]: [(1, 2), (6, 7)]

Сроки для 100000x увеличенного размера данных -

In [226]: mask = [1, 0, 0, 1, 1, 1, 0, 0]In [227]: mask = np.repeat(mask,100000)# Original soln
In [230]: %%timeit
     ...: segments = []
     ...: start = 0
     ...: for i in range(len(mask) - 1):
     ...:     e1 = mask[i]
     ...:     e2 = mask[i + 1]
     ...:     if e1 == 0 and e2 == 1:
     ...:         start = i + 1
     ...:     elif e1 == 1 and e2 == 0:
     ...:         segments.append((start, i))
1 loop, best of 3: 401 ms per loop# @Yakym Pirozhenko's soln
In [231]: %%timeit
     ...: slices = np.ma.clump_masked(np.ma.masked_where(mask, mask))
     ...: result = [(s.start, s.stop - 1) for s in slices]
100 loops, best of 3: 4.8 ms per loopIn [232]: %timeit start_stop(mask, trigger_val=1)
1000 loops, best of 3: 1.41 ms per loop
Aiven ответил: 28 апреля 2018 в 08:56
Я запускаю cProfile на моем решении и получил 6335 мс, а с вашим решением 1 мс. Я просто не могу в это поверить: D
Yakym Pirozhenko ответил: 28 апреля 2018 в 08:53

Альтернативный подход с np.ma.clump_masked.

mask = np.array([1, 0, 0, 1, 1, 1, 0, 0])
# get a list of "clumps" or contiguous slices.
slices = np.ma.clump_masked(np.ma.masked_where(mask, mask))
# convert each slice to a tuple of indices.
result = [(s.start, s.stop - 1) for s in slices]
# [(0, 0), (3, 5)]