Из 1-битного массива битов получить конкретный 2-битный массив последовательностей единиц [Python]

Question

Я использую Python, и мне нужно найти наиболее эффективный способ выполнить следующую задачу.

Задание: Для любого одномерного массива v нулей и единиц обозначить k > = 0 количество подпоследовательностей всехиз v .

Мне нужно получить из v двумерный массив w такой, что:
1) shape (w) = (k, len (v)),
2) для каждого i = 1, .., k i-я строка «w» является массивом всех нулей, кроме i-й подпоследовательности всех единиц из v .

Позвольте мне привести пример: предположим, что $ v $ это массив

v=[0,1,1,0,0,1,0,1,1,1]

Тогда k = 3 и w должен быть массивом

w=[[0,1,1,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,1,1,1]]

Можно написать код для выполнения этой задачи разными способами, например:

import numpy as np

start=[]
end=[]
for ii in range(len(v)-1):
    if (v[ii:ii+2]==[0,1]).all():
        start.append(ii)
    if (v[ii:ii+2]==[1,0]).all():
        end.append(ii)
if len(start)>len(end):
    end.append(len(v)-1)

w=np.zeros((len(start),len(v)))
for jj in range(len(start)):
    w[jj,start[jj]+1:end[jj]+1]=np.ones(end[jj]-start[jj])

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

Итак, в заключение мой вопрос: каков наиболее эффективный способ вычисления?выполнить это на Python?

Answer 1

Вот один векторизованный способ -

def expand_islands2D(v):
    # Get start, stop of 1s islands
    v1 = np.r_[0,v,0]
    idx = np.flatnonzero(v1[:-1] != v1[1:])
    s0,s1 = idx[::2],idx[1::2]

    # Initialize 1D id array  of size same as expected o/p and has 
    # starts and stops assigned as 1s and -1s, so that a final cumsum
    # gives us the desired o/p
    N,M = len(s0),len(v)
    out = np.zeros(N*M,dtype=int)

    # Setup starts with 1s
    r = np.arange(N)*M
    out[s0+r] = 1

    # Setup stops with -1s
    if s1[-1] == M:
        out[s1[:-1]+r[:-1]] = -1
    else:
        out[s1+r] = -1

    # Final cumsum on ID array
    out2D = out.cumsum().reshape(N,-1)
    return N, out2D 

Пробный прогон -

In [105]: v
Out[105]: array([0, 1, 1, 0, 0, 1, 0, 1, 1, 1])

In [106]: k,out2D = expand_islands2D(v)

In [107]: k # number of islands
Out[107]: 3

In [108]: out2D # 2d output with 1s islands on different rows
Out[108]: 
array([[0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 1, 1]])