numpy 2d булевая индексация массива с уменьшением вдоль одной оси

Question

Этот вопрос похож на this.

У меня есть 2d булевский массив «принадлежать» и 2d поплавковый массив «углы». То, что я хочу, состоит в том, чтобы суммировать вдоль строк углы, для которых принадлежит соответствующий индекс, - True, и делать это с помощью numpy (т. Е. Избегать циклов питона). Мне не нужно сохранять результирующие строки, которые будут иметь разную длину, и, как объяснено в связанном вопросе, потребуется список.

Так что я попытался сделать np.sum (углы [принадлежат], ось = 1), но углы [принадлежат] возвращают 1d результат, и я не могу уменьшить его, как я хочу. Я также попробовал np.sum (углы * принадлежат, ось = 1), и это работает. Но мне интересно, могу ли я улучшить время, обратившись только к индексам, где принадлежит True. принадлежат Истине около 30% времени, а углы - это упрощение более длинной формулы, которая включает в себя углы.

UPDATE

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

Это то, что я сделал:

THRES_THETA и max_line_length являются поплавки. принадлежат, угол и lines_lengths_vstacked имеют форму (1653, 58) и np.count_nonzero (принадлежат) /belong.size -> +0,376473287856979

l2 = (lambda angle=angle, belong=belong, THRES_THETA=THRES_THETA, lines_lengths_vstacked=lines_lengths_vstacked, max_line_length=max_line_length: 
     np.sum(belong*(0.3 * (1-(angle/THRES_THETA)) + 0.7 * (lines_lengths_vstacked/max_line_length)), axis=1)) #base method 
t2 = timeit.Timer(l2) 
print(t2.repeat(3, 100)) 

l1 = (lambda angle=angle, belong=belong, THRES_THETA=THRES_THETA, lines_lengths_vstacked=lines_lengths_vstacked, max_line_length=max_line_length: 
    np.einsum('ij,ij->i', belong, 0.3 * (1-(angle/THRES_THETA)) + 0.7 * (lines_lengths_vstacked/max_line_length))) 
t1 = timeit.Timer(l1) 
print(t1.repeat(3, 100)) 

l3 = (lambda angle=angle, belong=belong: 
    np.sum(angle*belong ,axis=1)) #base method 
t3 = timeit.Timer(l3) 
print(t3.repeat(3, 100)) 

l4 = (lambda angle=angle, belong=belong: 
    np.einsum('ij,ij->i', belong, angle)) 
t4 = timeit.Timer(l4) 
print(t4.repeat(3, 100)) 

и результаты были:

[0.2505458095931187, 0.22666162878242901, 0.23591678551324263] 
[0.23295411847036418, 0.21908727226505043, 0.22407296178704272] 
[0.03711204915708555, 0.03149960399994978, 0.033403337575027114] 
[0.025264803208228992, 0.022590580646423053, 0.024585736455331464] 

Если мы посмотрим в последних двух строках, соответствующая einsum, примерно на 30% быстрее, чем при использовании базового метода. Но если мы посмотрим на первые две строки, скорость для метода einsum будет меньше, примерно на 0,1% быстрее.

Я не уверен, что это время можно улучшить.

Answer 1

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

Я надеялся рассчитать формулу с углами только для позиций, где принадлежит True. Это должно ускориться примерно в 3 раза, так как истинно примерно в 30% случаев.

Моя первая попытка использования углов [принадлежит] будет вычислять формулу только для позиций, где принадлежит True, но имела проблему, что результирующий массив был равен 1d, и я не мог выполнять сокращения строк с помощью np.sum. Решение состоит в использовании np.add.reduceat.

reduceat может уменьшить ufunc (в данном случае добавить) в списке конкретных фрагментов. Поэтому мне просто нужно создать этот список срезов, чтобы я мог уменьшить 1d-массив из-за углов [принадлежат].

Я покажу свой код и тайминги, и это должно говорить само по себе.

Я сначала определить функцию с раствором reduceat:

def vote_op(angle, belong, THRES_THETA, lines_lengths_vstacked, max_line_length): 
    intermediate = (0.3 * (1-(angle[belong]/THRES_THETA)) + 0.7 * (lines_lengths_vstacked[belong]/max_line_length)) 
    b_ind = np.hstack([0, np.cumsum(np.sum(belong, axis=1))]) 
    votes = np.add.reduceat(intermediate, b_ind[:-1]) 
    return votes 

потом сравнить с методом базового и метода einsum:

l1 = (lambda angle=angle, belong=belong, THRES_THETA=THRES_THETA, lines_lengths_vstacked=lines_lengths_vstacked, max_line_length=max_line_length: 
     np.sum(belong*(0.3 * (1-(angle/THRES_THETA)) + 0.7 * (lines_lengths_vstacked/max_line_length)), axis=1)) 
t1 = timeit.Timer(l1) 
print(t1.repeat(3, 100)) 

l2 = (lambda angle=angle, belong=belong, THRES_THETA=THRES_THETA, lines_lengths_vstacked=lines_lengths_vstacked, max_line_length=max_line_length: 
    np.einsum('ij,ij->i', belong, 0.3 * (1-(angle/THRES_THETA)) + 0.7 * (lines_lengths_vstacked/max_line_length))) 
t2 = timeit.Timer(l2) 
print(t2.repeat(3, 100)) 

l3 = (lambda angle=angle, belong=belong, THRES_THETA=THRES_THETA, lines_lengths_vstacked=lines_lengths_vstacked, max_line_length=max_line_length: 
     vote_op(angle, belong, THRES_THETA, lines_lengths_vstacked, max_line_length)) 
t3 = timeit.Timer(l3) 
print(t3.repeat(3, 100)) 

и тайминги:

[2.866840408487671, 2.6822349628234874, 2.665520338478774] 
[2.3444239421490725, 2.352450520946098, 2.4150879511222794] 
[0.6846337313820605, 0.660780839464234, 0.6091473217964847] 

Таким образом, решение reduat составляет около 3 раз быстрее и дает те же результаты, что и два других. Обратите внимание, что эти результаты для немного большего, чем раньше, например, где: принадлежат, угол и lines_lengths_vstacked имеют форму: (3400, 170) и np.count_nonzero (принадлежат) /belong.size-> 0,16765051903114186

Обновление Из-за угла в np.reduceat (как в numpy version '1.11.0rc1'), где он не может корректно обрабатывать повторяющиеся индексы, see, мне пришлось добавить функцию hack для функции vote_op() для случая, когда целые строки принадлежат False. Это приводит к повторным индексам в b_ind и неправильным результатам в голосах. Мое решение на данный момент заключается в исправлении неправильных значений, которое работает, но это еще один шаг. см. new vote_op():

def vote_op(angle, belong, THRES_THETA, lines_lengths_vstacked, max_line_length): 
    intermediate = (0.3 * (1-(angle[belong]/THRES_THETA)) + 0.7 * (lines_lengths_vstacked[belong]/max_line_length)) 
    b_rows = np.sum(belong, axis=1) 
    b_ind = np.hstack([0, np.cumsum(b_rows)])[:-1] 
    intermediate = np.hstack([intermediate, 0]) 
    votes = np.add.reduceat(intermediate, b_ind) 
    votes[b_rows == 0] = 0 
    return votes 

Answer 2

Вы можете использовать masked arrays для этого, но в тестах я побежал это не быстрее, чем (angles * belong).sum(1).

маска подход массива будет выглядеть следующим образом:

sum_ang = np.ma.masked_where(~belong, angles, copy=False).sum(1).data 

Здесь мы создаем замаскированный массив angles где значения ~belong («не принадлежит»), которые маскируется (без НДС). Мы принимаем не, потому что мы хотим исключить значения в belong, которые являются False. Затем возьмите сумму вдоль строк .sum(1). sum вернет другой массив в масках, поэтому вы получите значения с атрибутом этого маскированного массива.

Я добавил copy=False kwarg, чтобы этот код не замедлился при создании массива, но он все еще медленнее, чем ваш подход (angles * belong).sum(1), поэтому вы, вероятно, должны просто придерживаться этого.

Answer 3

Вы можете использовать np.einsum -

np.einsum('ij,ij->i',belong,angles) 

Вы также можете использовать np.bincount, как так -

idx,_ = np.where(belong) 
out = np.bincount(idx,angles[belong]) 

пример работы -

In [32]: belong 
Out[32]: 
array([[ True, True, True, False, True], 
     [False, False, False, True, True], 
     [False, False, True, True, True], 
     [False, False, True, False, True]], dtype=bool) 

In [33]: angles 
Out[33]: 
array([[ 0.65429151, 0.36235607, 0.98316406, 0.08236384, 0.5576149 ], 
     [ 0.37890797, 0.60705112, 0.79411002, 0.6450942 , 0.57750073], 
     [ 0.6731019 , 0.18608778, 0.83387574, 0.80120389, 0.54971573], 
     [ 0.18971255, 0.86765132, 0.82994543, 0.62344429, 0.05207639]]) 

In [34]: np.sum(angles*belong ,axis=1) # This worked for you, so using as baseline 
Out[34]: array([ 2.55742654, 1.22259493, 2.18479536, 0.88202183]) 

In [35]: np.einsum('ij,ij->i',belong,angles) 
Out[35]: array([ 2.55742654, 1.22259493, 2.18479536, 0.88202183]) 

In [36]: idx,_ = np.where(belong) 
    ...: out = np.bincount(idx,angles[belong]) 
    ...: 

In [37]: out 
Out[37]: array([ 2.55742654, 1.22259493, 2.18479536, 0.88202183]) 

Продолжительность испытания -

In [52]: def sum_based(belong,angles): 
    ...:  return np.sum(angles*belong ,axis=1) 
    ...: 
    ...: def einsum_based(belong,angles): 
    ...:  return np.einsum('ij,ij->i',belong,angles) 
    ...: 
    ...: def bincount_based(belong,angles): 
    ...:  idx,_ = np.where(belong) 
    ...:  return np.bincount(idx,angles[belong]) 
    ...: 

In [53]: # Inputs 
    ...: belong = np.random.rand(4000,5000)>0.7 
    ...: angles = np.random.rand(4000,5000) 
    ...: 

In [54]: %timeit sum_based(belong,angles) 
    ...: %timeit einsum_based(belong,angles) 
    ...: %timeit bincount_based(belong,angles) 
    ...: 
1 loops, best of 3: 308 ms per loop 
10 loops, best of 3: 134 ms per loop 
1 loops, best of 3: 554 ms per loop 

Я бы пошел с np.einsum один!