Python - Как быстро найти индекс нескольких векторов в массиве

#python #numpy

Вопрос:

У меня есть 2 больших массива, A и B , и я хочу найти, где находятся векторы A B . Мне нужно найти 10 000, 1 x 800 векторов среди 40 000 векторов одинакового размера.

Пример

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

Желаемый результат:

 [1,2]

Я могу найти один вектор, используя np.argwhere((A == B[0]).all(-1)) , но я не уверен, как сформировать массивы, чтобы найти индексы каждого вектора. Я могу использовать цикл for, но это слишком медленно. Например

 np.asarray([np.argwhere((A == B_[i]).all(-1)) for i in range(np.shape(A)[0])])

1. Вы неправильно указали формы. Но, используя enumerate, вы могли бы создать словарь из B , с помощью векторов и чьи значения являются индексами, в которых встречается вектор. Что-то вроде d = {v:i for i,v in enumerate(B)} . Это позволило бы вам просто искать, где векторы встречаются в B

2. How can I do this without a for loop? — проведите некоторое исследование; сформулируйте некоторые стратегии; попробуйте их; оцените; скорректируйте; повторите.

3. A и B — это не один и тот же массив. Я переформулировал вопрос, чтобы отразить это.

4. Я не хочу использовать enumerate, потому что это фактически цикл for . У меня примерно 10 000 векторов, поэтому использование цикла for не представляется возможным.

5. При таком времени выполнения я предполагаю, что вы используете что-то, имеющее квадратичную сложность. Мое предложение сводит его к линейному.

Ответ №1:

Настройка

 import numpy as np

rows_a = 40000
rows_b = 10000
size = 800

a = np.arange(rows_a * size).reshape((rows_a, size))
np.random.shuffle(a)
b = np.arange(rows_b * size).reshape((rows_b, size))

Решение

 d = {tuple(v): i for i, v in enumerate(a)}
idx = [d[tuple(row)] for row in b]

Допустим, что a имеет размер m и b имеет размер n .

d создает сопоставление строк в a их индексе. tuple(v) необходимо, если v не является хешируемым, например, списки и ndarrays. Это имеет O (m) временную сложность, потому что вы перебираете строки один раз.

idx выполняет итерацию по строкам b и проверяет словарь , чтобы получить соответствующий индекс a . Поиск по словарю имеет временную сложность O (1) и цикл O (n). В общем, вы смотрите на O (m n), который является линейным.

Вместо этого вы делаете так: для каждой строки b вы проверяете каждую строку, a чтобы найти ее индекс. Это имеет сложность O (m * n), которая является квадратичной.