重复上一个索引

Question

我有一个指标数组a，它包含一个1，如果最后一个0的索引应该被复制。否则，当前运行索引将通过：

也就是说

a = np.array([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1])
i = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

预期产量

x = np.array([0, 0, 0, 0, 4, 5, 6, 6, 6, 9, 9])

再次说明：逻辑：

• 到达索引y
• • Ifa[y] == 0：返回i[y]
• • Ifa[y] == 1：返回i[yy]，其中yy是max yy < y: a[yy] == 0-其中a是0的“上一个索引”。你知道吗

a[0] == 0，总是。你知道吗

我设法完成的任何方法都使用递归方法/循环，而且根本没有效率。什么是快速计算x？你知道吗

Answer 1

为了快速编写代码，我知道应该使用可能性较小的if、no for（包含while和try/except）、预分配变量，并使用numpy数组。你知道吗

a = np.array([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1])
i = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
x = np.zeros(len(a))
for j, aa in enumerate(a):
    if j == 0:
        x[j] == aa
    elif aa == 1:
        x[j] = x[j-1]
    else: 
        x[j] = i[j]

Answer 2

这里有一种使用masking和maximum-accumulation与np.maximum.accumulate的矢量化方法-

i[np.maximum.accumulate(np.where(a==0, np.arange(len(a)), 0))]

另一种说法是-

i[np.maximum.accumulate(np.arange(len(a)) * (a==0))]

解释

为了深入了解故事的细节，我们来分解一下步骤-

1]输入：

In [83]: a = np.array([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1])
    ...: i = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    ...: 

2]所以，输入a是：

In [84]: a
Out[84]: array([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1])

3]获取覆盖长度为a的范围数组：

In [85]: np.arange(len(a))
Out[85]: array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10])

4]现在在a为1的位置屏蔽范围数组，留下与a为0对应的元素：

In [86]: np.arange(len(a)) * (a==0)
Out[86]: array([0, 0, 0, 0, 4, 5, 6, 0, 0, 9, 0])

5]根据需要使用最大累积量来创建斜坡结构：

In [87]: np.maximum.accumulate(np.arange(len(a)) * (a==0))
Out[87]: array([0, 0, 0, 0, 4, 5, 6, 6, 6, 9, 9])

6]最后用这些数字索引到i中，以获得所需的输出：

In [88]: i[np.maximum.accumulate(np.arange(len(a)) * (a==0))]
Out[88]: array([0, 0, 0, 0, 4, 5, 6, 6, 6, 9, 9])

运行时测试

接近-

def FranciscoRodriguez(a,i): # @Francisco Rodríguez's soln
    x = []
    for idx,val in enumerate(a):
        if val==0: x.append(i[idx])
        elif val==1: x.append(x[-1])
    return x

def ThomasGuenet(a,i): # @ThomasGuenet 's soln
    x = np.zeros(len(a))
    for j, aa in enumerate(a):
        if j == 0:
            x[j] == aa
        elif aa == 1:
            x[j] = x[j-1]
        else: 
            x[j] = i[j]
    return x

def vectorizedApp1(a,i):
    return i[np.maximum.accumulate(np.where(a==0, np.arange(len(a)), 0))]

def vectorizedApp2(a,i):
    return i[np.maximum.accumulate(np.arange(len(a)) * (a==0))]

计时-

让我们平铺给定的示例以创建更大的数据集，并测试所有解决方案：

In [78]: a = np.array([0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1])
    ...: i = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    ...: 
    ...: a = np.tile(a,100000)
    ...: i = np.tile(i,100000)
    ...: 

In [79]: %timeit FranciscoRodriguez(a,i)
    ...: %timeit ThomasGuenet(a,i)
    ...: %timeit vectorizedApp1(a,i)
    ...: %timeit vectorizedApp2(a,i)
    ...: 
1 loop, best of 3: 328 ms per loop
1 loop, best of 3: 331 ms per loop
100 loops, best of 3: 6.07 ms per loop
100 loops, best of 3: 6.77 ms per loop

Answer 3

我这样做：

a = [0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1]
i = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
x = []
for idx,val in enumerate(a):
    if val==0: x.append(i[idx])
    elif val==1: x.append(x[-1])

它是一个只在列表中迭代一次的循环，因此没有嵌套循环或递归。这样的话，时间成本将是O（N），N是a的长度