Нахождение пересечения между матрицей и вектором, по строке

Question

Рассмотрим следующее:

tmp1 = ['a', 'b', 'c', 'd', 'e']
tmp2 = ['f', 'g', 'h', 'b', 'd']
tmp3 = ['b', 'i', 'j', 'k', 'l']
matr = np.array([tmp1, tmp2, tmp3])

matr

Выходит матрица:

array([['a', 'b', 'c', 'd', 'e'],
   ['f', 'g', 'h', 'b', 'd'],
   ['b', 'i', 'j', 'k', 'l']], 
  dtype='|S1')

Теперь я хочу узнать сумму значений в каждой строке, которая пересекает вектор. Скажи,

vec = ['a', 'c', 'f', 'b']
[sum([y in vec for y in row]) for row in matr]

Returns

[3, 2, 1]

Это желаемый результат. Проблема в том, что мой 'matr' на самом деле равен ≈ 1000000 x 2200, и у меня есть 6700 векторов для сравнения. Решение, которое я здесь нашел, слишком медленное, чтобы пытаться.

Как я могу улучшить то, что я делаю?

Стоит отметить, что значения внутри matr берутся из набора ~ 30000 значений, и у меня есть полный набор. Я рассмотрел решения, в которых я определяю эти 30000 значений для каждого вектора и использую их для преобразования в True / False по всей матрице перед простым суммированием по строке. Я не уверен, поможет ли это.

Answer 1

Вы можете использовать набор пересечения, чтобы немного ускорить процесс. Вот сравнение:

Ваше настоящее решение со списком:

%%timeit
print([sum([y in vec for y in row]) for row in matr])
#Output
[3,2,1]
20 µs ± 1.9 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Предлагаемое решение с заданным пересечением в понимании списка:

%%timeit
print([len(set(row).intersection(vec)) for row in matr])
#Output:
[3,2,1]
17.8 µs ± 1.46 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

И если vec также является набором, мы получаем еще лучшую эффективность:

%%timeit
vec = {'a', 'c', 'f', 'b'}
print([len(set(row).intersection(vec)) for row in matr])
#Output:
[3, 2, 1]
16.6 µs ± 1.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 2

Для matr и vec в качестве массивов, вот один с np.searchsorted -

def count_in_rowwise(matr,vec):
    sidx = vec.argsort()
    idx = np.searchsorted(vec,matr,sorter=sidx)
    idx[idx==len(vec)] = 0
    return (vec[sidx[idx]] == matr).sum(1)

При сравнительно меньшем vec мы можем предварительно отсортировать егои использовать, чтобы дать нам альтернативный способ вычисления количества строк, например так:

def count_in_rowwise_v2(matr,vec,assume_sorted=False):
    if assume_sorted==1:
        sorted_vec = vec
    else:
        sorted_vec = np.sort(vec)
    idx = np.searchsorted(sorted_vec,matr)
    idx[idx==len(sorted_vec)] = 0
    return (sorted_vec[idx] == matr).sum(1)

Приведенные выше решения работают с общими входными данными (одинаковыми числами или строками).Чтобы решить наш конкретный случай строк, мы могли бы еще больше оптимизировать его, преобразовав строки в числа, используя np.unique, а затем повторно используя count_in_rowwise/count_in_rowwise_v2, и это даст нам наш второй подход, например, -

u,ids = np.unique(matr, return_inverse=True)
out = count_in_rowwise(ids.reshape(matr.shape),ids[np.searchsorted(u,vec)])

Answer 3

Давайте посмотрим на скорость вашего текущего алгоритма. Согласно вики Python, проверка, находится ли элемент в массиве, подобном y in vec, равен O (n), что означает наихудший случай, он должен пройти через каждый элемент в vec. Поскольку вы выполняете эту проверку для каждого элемента вашей матрицы, общее количество операций составляет numRows * numCols * vecLen, что составляет O(n^3).

Более быстрый способ сделать это - создать словарь для vec, чтобы оптимизировать поиск, потому что словари O(1) вместо O(n), что означает, что они могут выполнить вашу проверку за 1 операцию, независимо от того, какой длины vec:

vecDict = dict([(x, 1) for x in vec])

Итак, ваша новая временная сложность - (numRows * numCols) + vecLen, то есть O(n^2), что, я думаю, так быстро, как вы можете получить ваши данные.

[sum([y in vecDict for y in row]) for row in matr]

Answer 4

Вот простое удобочитаемое решение с np.isin() ( документами ):

np.sum(np.isin(matr, vec), axis=1)

В качестве бонуса вы можете просто использовать np.isin() без суммирования, если хотите получитькакие элементы матрицы находятся в векторах:

>>> np.isin(matr, vec)
array([[ True,  True,  True, False, False],
       [ True, False, False,  True, False],
       [ True, False, False, False, False]])

, что показывает, почему суммирование по строкам дает желаемый результат.