#python #numpy
#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), которая является квадратичной.