Накопить сумму нерегулярных срезов в массиве

Question

Мне нужно быстро обработать огромный двумерный массив и уже предварительно пометить необходимые данные.

array([[  0.,   1.,   2.,   3.,   4.,   5. ,   6. ,   7.],
       [  6.,   7.,   8.,   9.,  10.,   4.2,   4.3,  11.],
       [ 12.,  13.,  14.,  15.,  16.,   4.2,   4.3,  17.],
       [ 18.,  19.,  20.,  21.,  22.,   4.2,   4.3,  23.]])

array([[False, True,  True,  True, False, True, True , False],
       [False, False, False, True,  True, True, True , False],
       [False, False, True, True, False, False, False, False],
       [False, True, True, False, False, False, True , True ]])

Я ожидаю суммирования данных маркеров в каждой строке массива. Но np.cumsum не может этого сделать, мне нужны решения или хорошие идеи, спасибо

Ожидаемый результат:

array([[  0.,   1.,   3.,   6.,   0.,   5. ,   11. ,    0.],
       [  0.,   0.,   0.,   9.,  19.,  23.2,   27.5,    0.],
       [  0.,   0.,  14.,  29.,   0.,     0,      0,    0.],
       [  0.,  19.,  39.,   0.,   0.,     0,     4.3, 27.3]])

Сложность решения состоит в том, что каждый фрагмент не может содержать результат предыдущего фрагмента

def mask_to_size(self,axis=-1):
    if self.ndim==2:
        if axis == 0:
            mask = np.zeros((self.shape[0]+1,self.shape[1]), dtype=bool)
            mask[:-1] = self ; mask[0] = False ; mask = mask.ravel('F') 
        else:
            mask = np.zeros((self.shape[0],self.shape[1]+1), dtype=bool)
            mask[:,0:-1]= self ;mask[:,0]=False; mask = mask.ravel('C')
    else:
        mask = np.zeros((self.shape[0]+1), dtype=bool)
        mask[:-1] = self ; mask[0] = False
    return np.diff(np.nonzero(mask[1:]!= mask[:-1])[0])[::2].astype(int)

# https://stackoverflow.com/a/49179628/  by @Divakar
def intervaled_cumsum(ar, sizes):
    out = ar.copy() 
    arc = ar.cumsum() ; idx = sizes.cumsum()
    out[idx[0]] = ar[idx[0]] - arc[idx[0]-1]
    out[idx[1:-1]] = ar[idx[1:-1]] - np.diff(arc[idx[:-1]-1])
    return out.cumsum()  

def cumsum_masked(self,mask,axis=-1):
    sizes = mask_to_size(mask,axis);out = np.zeros(self.size);shape = self.shape
    if len(shape)==2:
        if axis == 0:
            mask = mask.ravel('F') ; self = self.ravel('F')
        else:
            mask = mask.ravel('C') ; self = self.ravel('C')
    out[mask] = intervaled_cumsum(self[mask],sizes)
    if len(shape)==2:
        if axis == 0:
            return out.reshape(shape[1],shape[0]).T
        else:
            return out.reshape(shape)
    return out

cumsum_masked(a,m,axis=1)

Я разобрался с ответами и попытался оптимизировать скорость, но это не сработало. Я думаю, что это может понадобиться другим людям.

Answer 1

Для 1D массивов intervaled_cumsum. Для этого случая нам просто нужно получить замаскированные элементы, настроить их длину островков и передать их этой функции.

Следовательно, один векторизованный подход будет -

# https://stackoverflow.com/a/49179628/  by @Divakar
def intervaled_cumsum(ar, sizes):
    # Make a copy to be used as output array
    out = ar.copy()

    # Get cumumlative values of array
    arc = ar.cumsum()

    # Get cumsumed indices to be used to place differentiated values into
    # input array's copy
    idx = sizes.cumsum()

    # Place differentiated values that when cumumlatively summed later on would
    # give us the desired intervaled cumsum
    out[idx[0]] = ar[idx[0]] - arc[idx[0]-1]
    out[idx[1:-1]] = ar[idx[1:-1]] - np.diff(arc[idx[:-1]-1])
    return out.cumsum()  

def intervaled_cumsum_masked_rowwise(a, mask):
    z = np.zeros((mask.shape[0],1), dtype=bool)
    maskz = np.hstack((z,mask,z))

    out = np.zeros_like(a)
    sizes = np.diff(np.flatnonzero(maskz[:,1:] != maskz[:,:-1]))[::2]
    out[mask] = intervaled_cumsum(a[mask], sizes)
    return out  

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

In [95]: a
Out[95]: 
array([[ 0. ,  1. ,  2. ,  3. ,  4. ,  5. ,  6. ,  7. ],
       [ 6. ,  7. ,  8. ,  9. , 10. ,  4.2,  4.3, 11. ],
       [12. , 13. , 14. , 15. , 16. ,  4.2,  4.3, 17. ],
       [18. , 19. , 20. , 21. , 22. ,  4.2,  4.3, 23. ]])

In [96]: mask
Out[96]: 
array([[False,  True,  True,  True, False,  True,  True, False],
       [False, False, False,  True,  True,  True,  True, False],
       [False, False,  True,  True, False, False, False, False],
       [False,  True,  True, False, False, False,  True,  True]])

In [97]: intervaled_cumsum_masked_rowwise(a, mask)
Out[97]: 
array([[ 0. ,  1. ,  3. ,  6. ,  0. ,  5. , 11. ,  0. ],
       [ 0. ,  0. ,  0. ,  9. , 19. , 23.2, 27.5,  0. ],
       [ 0. ,  0. , 14. , 29. ,  0. ,  0. ,  0. ,  0. ],
       [ 0. , 19. , 39. ,  0. ,  0. ,  0. ,  4.3, 27.3]])

Работает так же хорошо с отрицательными числами -

In [109]: a = -a

In [110]: a
Out[110]: 
array([[ -0. ,  -1. ,  -2. ,  -3. ,  -4. ,  -5. ,  -6. ,  -7. ],
       [ -6. ,  -7. ,  -8. ,  -9. , -10. ,  -4.2,  -4.3, -11. ],
       [-12. , -13. , -14. , -15. , -16. ,  -4.2,  -4.3, -17. ],
       [-18. , -19. , -20. , -21. , -22. ,  -4.2,  -4.3, -23. ]])

In [111]: intervaled_cumsum_masked_rowwise(a, mask)
Out[111]: 
array([[  0. ,  -1. ,  -3. ,  -6. ,   0. ,  -5. , -11. ,   0. ],
       [  0. ,   0. ,   0. ,  -9. , -19. , -23.2, -27.5,   0. ],
       [  0. ,   0. , -14. , -29. ,   0. ,   0. ,   0. ,   0. ],
       [  0. , -19. , -39. ,   0. ,   0. ,   0. ,  -4.3, -27.3]])

Answer 2

Вот подход, который немного медленнее, чем у @ Divakar's и @ filippo, но более надежный. Проблема с подходами «глобальной кончины» заключается в том, что они могут страдать от потери значимости, см. Ниже:

import numpy as np
from scipy import linalg

def cumsums(data, mask, break_lines=True):
    dr = data[mask]
    if break_lines:
        msk = mask.copy()
        msk[:, 0] = False
        mr = msk.ravel()[1:][mask.ravel()[:-1]][:dr.size-1]
    else:
        mr = mask.ravel()[1:][mask.ravel()[:-1]][:dr.size-1]
    D = np.empty((2, dr.size))
    D.T[...] = 1, 0
    D[1, :-1] -= mr
    out = np.zeros_like(data)
    out[mask] = linalg.solve_banded((1, 0), D, dr)
    return out

def f_staircase(a, m):
    return np.cumsum(a, axis=1) - np.maximum.accumulate(np.cumsum(a, axis=1)*~m, axis=1)

# https://stackoverflow.com/a/49179628/  by @Divakar
def intervaled_cumsum(ar, sizes):
    # Make a copy to be used as output array
    out = ar.copy()

    # Get cumumlative values of array
    arc = ar.cumsum()

    # Get cumsumed indices to be used to place differentiated values into
    # input array's copy
    idx = sizes.cumsum()

    # Place differentiated values that when cumumlatively summed later on would
    # give us the desired intervaled cumsum
    out[idx[0]] = ar[idx[0]] - arc[idx[0]-1]
    out[idx[1:-1]] = ar[idx[1:-1]] - np.diff(arc[idx[:-1]-1])
    return out.cumsum()  

def intervaled_cumsum_masked_rowwise(a, mask):
    z = np.zeros((mask.shape[0],1), dtype=bool)
    maskz = np.hstack((z,mask,z))

    out = np.zeros_like(a)
    sizes = np.diff(np.flatnonzero(maskz[:,1:] != maskz[:,:-1]))[::2]
    out[mask] = intervaled_cumsum(a[mask], sizes)
    return out  

data = np.array([[  0.,   1.,   2.,   3.,   4.,   5. ,   6. ,   7.],
                 [  6.,   7.,   8.,   9.,  10.,   4.2,   4.3,  11.],
                 [ 12.,  13.,  14.,  15.,  16.,   4.2,   4.3,  17.],
                 [ 18.,  19.,  20.,  21.,  22.,   4.2,   4.3,  23.]])

mask = np.array([[False, True,  True,  True, False, True, True , False],
                 [False, False, False, True,  True, True, True , False],
                 [False, False, True, True, False, False, False, False],
                 [False, True, True, False, False, False, True , True ]])

from timeit import timeit

print('fast?')
print('filippo', timeit(lambda: f_staircase(data, mask), number=1000))
print('pp     ', timeit(lambda: cumsums(data, mask), number=1000))
print('divakar', timeit(lambda: intervaled_cumsum_masked_rowwise(data, mask), number=1000))

data = np.random.uniform(-10, 10, (5000, 5000))
mask = np.random.random((5000, 5000)) < 0.125
mask[:, 1:] |= mask[:, :-1]
mask[:, 2:] |= mask[:, :-2]

print()
print('fast on large data?')
print('filippo', timeit(lambda: f_staircase(data, mask), number=3))
print('pp     ', timeit(lambda: cumsums(data, mask), number=3))
print('divakar', timeit(lambda: intervaled_cumsum_masked_rowwise(data, mask), number=3))

data = np.random.uniform(-10, 10, (10000, 10000))
mask = np.random.random((10000, 10000)) < 0.025
mask[:, 1:] |= mask[:, :-1]
mask[:, 2:] |= mask[:, :-2]

print()
print('fast on large sparse data?')
print('filippo', timeit(lambda: f_staircase(data, mask), number=3))
print('pp     ', timeit(lambda: cumsums(data, mask), number=3))
print('divakar', timeit(lambda: intervaled_cumsum_masked_rowwise(data, mask), number=3))

data = np.exp(-np.linspace(-24, 24, 100))[None]
mask = (np.arange(100) % 4).astype(bool)[None]

print()
print('numerically sound?')
print('correct', data[0, -3:].sum())
print('filippo', f_staircase(data, mask)[0,-1]) 
print('pp     ', cumsums(data, mask)[0,-1])
print('divakar', intervaled_cumsum_masked_rowwise(data, mask)[0,-1])

Выход:

fast?
filippo 0.008435532916337252
pp      0.07329772273078561
divakar 0.0336935929954052

fast on large data?
filippo 1.6037923698313534
pp      3.982803522143513
divakar 1.706403402145952

fast on large sparse data?
filippo 6.11361704999581
pp      4.717669038102031
divakar 2.9474888620898128

numerically sound?
correct 1.9861262739950047e-10
filippo 0.0
pp      1.9861262739950047e-10
divakar 9.737630365237156e-06

Мы видим, что на падающем показательном примере подходы, основанные на сумме, не работают. Очевидно, это искусственный пример, но он демонстрирует реальную проблему.

Answer 3

Вот попытка реализовать предложение @hpaulj

>>> a = np.array([[ 0. ,  1. ,  2. ,  3. ,  4. ,  5. ,  6. ,  7. ],
...               [ 6. ,  7. ,  8. ,  9. , 10. ,  4.2,  4.3, 11. ],
...               [12. , 13. , 14. , 15. , 16. ,  4.2,  4.3, 17. ],
...               [18. , 19. , 20. , 21. , 22. ,  4.2,  4.3, 23. ]])

>>> m = np.array([[False,  True,  True,  True, False,  True,  True, False],
...               [False, False, False,  True,  True,  True,  True, False],
...               [False, False,  True,  True, False, False, False, False],
...               [False,  True,  True, False, False, False,  True,  True]])

>>> np.maximum.accumulate(np.cumsum(a, axis=1)*~m, axis=1)
array([[  0. ,   0. ,   0. ,   0. ,  10. ,  10. ,  10. ,  28. ],
       [  6. ,  13. ,  21. ,  21. ,  21. ,  21. ,  21. ,  59.5],
       [ 12. ,  25. ,  25. ,  25. ,  70. ,  74.2,  78.5,  95.5],
       [ 18. ,  18. ,  18. ,  78. , 100. , 104.2, 104.2, 104.2]])

>>> np.cumsum(a, axis=1) - np.maximum.accumulate(np.cumsum(a, axis=1)*~m, axis=1)
array([[ 0. ,  1. ,  3. ,  6. ,  0. ,  5. , 11. ,  0. ],
       [ 0. ,  0. ,  0. ,  9. , 19. , 23.2, 27.5,  0. ],
       [ 0. ,  0. , 14. , 29. ,  0. ,  0. ,  0. ,  0. ],
       [ 0. , 19. , 39. ,  0. ,  0. ,  0. ,  4.3, 27.3]])

См. Также Самый эффективный способ для прямой заливки значений NaN в массиве numpy , который кажется несколько связанным, особенно если ваш массивне >= 0, как в этом игрушечном примере, одобренный ответ там должен быть полезным.

РЕДАКТИРОВАТЬ Для дальнейшего использования здесь есть версия, которая удаляет вышеприведенное предположение >= 0.Тем не менее, он должен быть довольно быстрым, но не сравнивать его с другими методами.

In [38]: def masked_cumsum(a, m):                                                               
    ...:     idx = np.maximum.accumulate(np.where(m, 0, np.arange(m.size).reshape(m.shape)), axis=1)
    ...:     c = np.cumsum(a, axis=-1)                                                    
    ...:     return c - c[np.unravel_index(idx, m.shape)]
    ...: 

In [43]: masked_cumsum(-a, m)
Out[43]: 
array([[  0. ,  -1. ,  -3. ,  -6. ,   0. ,  -5. , -11. ,   0. ],
       [  0. ,   0. ,   0. ,  -9. , -19. , -23.2, -27.5,   0. ],
       [  0. ,   0. , -14. , -29. ,   0. ,   0. ,   0. ,   0. ],
       [  0. , -19. , -39. ,   0. ,   0. ,   0. ,  -4.3, -27.3]])