Более быстрое сравнение вложенных строк с массивами 2D numpy

Question

У меня есть два очень больших массива X_pos и X_neg с размерами (900000,100) и (1200000,100). Я хотел бы узнать, присутствует ли какой-либо элемент строки arr1 на arr2. Если есть совпадение, мне нужен список индексов для совпадающих строк. Позже мне нужно удалить их и сделать так, чтобы оба массива не совпадали с одинаковыми строками. На данный момент я использую for циклы:

list_conflict=[]
for i in range (len(X_pos)):
    for j in range (len(X_neg)):
        if (X_pos[i]==X_neg[j]):
            list_conflict.append([i,j])

fault_index_pos = np.unique([x[0] for x in list_conflict])
fault_index_neg = np.unique([x[1] for x in list_conflict])

X_neg = np.delete(X_neg,fault_index_neg,axis=0)
X_pos = np.delete(X_pos,fault_index_pos,axis=0)

Он берет элемент X_pos на внешнем l oop и полностью сравнивает его с каждым элементом X_neg. Если найдено совпадение, добавляются индексы list_conflict с первым элементом, занимающим позицию X_pos, а вторым X_pos. Затем fault_index_pos и fault_index_neg сжимаются в уникальные элементы, поскольку элемент X_pos может находиться в нескольких местах X_pos, а список будет иметь повторяющиеся позиции. Наконец, совпадающие элементы удаляются с помощью np.delete, принимая fault_index списки в качестве индекса для удаления.

Я ищу более быстрый подход для сравнения конфликтов, назовите его set, vectorization или что-то еще else.

PS Примеры массивов:

X_pos

array([[0,1,2,3,4],[0,1,2,3,5],[0,1,2,3,6],[2,4,5,6,7]])

X_neg

array([[2,4,5,6,7],[0,1,2,3,7],[0,1,2,3,4],[0,1,2,3,9],[1,9,3,2,5]])

Он должен вернуть индексы, которые дублируются в другом массиве, который равен list_conflict = [[0,1],[3,1]]. Затем по этим индексам я смогу удалить одинаковые элементы в обоих массивах. Возможный повторяющийся вопрос - это то, что я задал вчера, но он не дает точного объяснения проблемы с ненужным упрощением. Эти ответы не являются решением этой проблемы, и их пришлось как-то изменить, чтобы они сработали.

Answer 1

Найдите строки, в которых a содержит строки из b:

duplicate_a = np.isin(a, b).all(axis=1)

Для этих строк найдите соответствующие строки в b:

duplicate_b = np.isin(b, a[duplicate_a, :]).all(axis=1)

, чтобы получить индексы эти дубликаты:

duplicate_b_rows = b[duplicate_b]

duplicate_b_indices = duplicate_b.nonzero()[0]
duplicate_a_indices = duplicate_a.nonzero()[0]

duplicates = [
    (duplicate_a_indices[i], duplicate_b_indices[np.isin(duplicate_b_rows, row).all(axis=1)])
    for i, row in enumerate(a[duplicate_a, :])
]

Например,

a = np.random.random((1000, 100))
b = np.random.random((500, 100))
b[1, :] = a[3, :]
b[5, :] = a[3, :]
b[2, :] = a[1, :]

Выводит

[(1, array([2])), (3, array([1, 5]))]

, указывая, что a [1,:] соответствует b [2,: ], а a [3,:] соответствует b [1,:], а также b [5,:].

Чтобы полностью сгладить это:

duplicates = [
    (duplicate_a_indices[i], duplicate_b_indices[j])
    for i, row in enumerate(a[duplicate_a, :]) for j in np.isin(duplicate_b_rows, row).all(axis=1).nonzero()[0]
]

Было бы теперь выведите [(1, 2), (3, 1), (3, 5)] для приведенного выше примера

Но более быстрым способом было бы использовать таблицу поиска для строк:

a_lookup = {row.tostring(): i for i, row in enumerate(a)}

duplicates = [(a_lookup[row.tostring()], i) for i, row in enumerate(b) if row.tostring() in a_lookup]

Это работает намного быстрее, чем версия numpy в если у вас много строк, так как сложность равна O(N*K + M*K)), где N и M - это количество строк в a и b соответственно, а K - количество элементов в строке.

Хотя сложность решения numpy составляет O(M*N*K).

Обратите внимание, что это будет нормально работать для поиска точных дубликатов, но если ваши данные состоят из чисел с плавающей запятой, вы можете пропустить «дубликат» s ", которые по существу одинаковы, но из-за ограниченного разрешения поплавка будут отличаться на di git или более.