python - 从 1 维位数组中获取特定的 2 维序列数组 [Python]

Question

我正在使用 Python，我需要找到最有效的方法来执行以下任务。

任务:给定任何由零和一组成的一维数组v，用k>=0表示所有的子序列的数量v 中的一个。

我需要从v获取一个二维数组w，这样:
1) 形状(w)=(k,len(v)),
2) 对于每个 i=1,..,k，“w”的第 i 行除了 v 的第 i 个全 1 子序列之外都是全 0 的数组。 p>

让我举个例子:假设 $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]])