Как эффективно суммировать вхождения значения в одном массиве в позиции в другом массиве

Question

Я ищу эффективное решение для обхода цикла, которое решает проблему, связанную с массивами. Я хочу использовать огромный 1Darray (A -> size = 250.000) значений от 0 до 40 для индексации в одном измерении и массив (B) того же размера со значениями от 0 до 9995 для индексации во втором измерении.

Результатом должен быть массив с размером (41, 9996), в котором для каждого индекса указано, сколько раз любое значение из массива 1 встречается со значением из массива 2.

Пример:

A = [0, 3, 2, 4, 3]
B = [1, 2, 2, 0, 2]
which should result in:
[[0, 1, 0,
 [0, 0, 0,
 [0, 0, 1,
 [0, 0, 2,
 [1, 0, 0]] 

Грязный путь слишком медленный, так как объем данных огромен, что вы могли бы сделать:

out = np.zeros(41,9995)
for i in A:
  for j in B:
     out[i,j] += 1 

, что займет 238 000 * 238 000 циклов ... Я пробовал это, который работает частично:

out = np.zeros(41,9995)
out[A,B] += 1

, который генерирует результат с 1 везде, независимо от того, сколько раз встречаются значения.

Кто-нибудь знает, как это исправить? Заранее спасибо!

Answer 1

Вы ищете разреженный тензор :

import torch

A = [0, 3, 2, 4, 3]
B = [1, 2, 2, 0, 2]
idx = torch.LongTensor([A, B])
torch.sparse.FloatTensor(idx, torch.ones(idx.shape[1]), torch.Size([5,3])).to_dense()

Выход:

tensor([[0., 1., 0.],
        [0., 0., 0.],
        [0., 0., 1.],
        [0., 0., 2.],
        [1., 0., 0.]])

Вы также можете сделать то же самое с scipy разреженная матрица :

import numpy as np
from scipy.sparse import coo_matrix

coo_matrix((np.ones(len(A)), (np.array(A), np.array(B))), shape=(5,3)).toarray()

output:

array([[0., 1., 0.],
       [0., 0., 0.],
       [0., 0., 1.],
       [0., 0., 2.],
       [1., 0., 0.]])

Иногда лучше оставить матрицу в ее разреженном представлении, а нечем заставить его быть "плотным" снова.

Answer 2

Учитывая, что числа находятся в небольшом диапазоне, bincount будет хорошим выбором для суммирования на основе бина -

def accumulate_coords(A,B):
    nrows = A.max()+1
    ncols = B.max()+1
    return np.bincount(A*ncols+B,minlength=nrows*ncols).reshape(-1,ncols)

Образец прогона -

In [55]: A
Out[55]: array([0, 3, 2, 4, 3])

In [56]: B
Out[56]: array([1, 2, 2, 0, 2])

In [58]: accumulate_coords(A,B)
Out[58]: 
array([[0, 1, 0],
       [0, 0, 0],
       [0, 0, 1],
       [0, 0, 2],
       [1, 0, 0]])

Answer 3

Использование numpy.add.at :

import numpy as np

A = [0, 3, 2, 4, 3]
B = [1, 2, 2, 0, 2]

arr = np.zeros((5, 3))
np.add.at(arr, (A, B), 1)

print(arr)

Выход

[[0. 1. 0.]
 [0. 0. 0.]
 [0. 0. 1.]
 [0. 0. 2.]
 [1. 0. 0.]]