Ускорение вложенного сравнения l oop

Question

У меня есть два массива arr1 и arr2 с размерами (90000,1) и (120000,1). Я хотел бы узнать, присутствует ли какой-либо элемент axis=0 из arr1 на arr2. Затем запишите их позиции в список, а затем удалите их. Это гарантирует, что ни один из элементов одного списка не может быть найден в другом. На данный момент я использую for циклы:

list_conflict=[]
for i in range (len(arr1)):
    for j in range (len(arr2)):
        if (arr1[i]==arr2[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)

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

Я ищу более быстрый подход для сравнения конфликтов, назовите его multiprocessing, vectorization или что-то еще еще. Можно сказать, что это не займет много времени, но на самом деле массивы имеют размер (x,8,10), но я сократил их для ясности.

Answer 1

Игнорируя часть numpy, обнаружение конфликтующих пар индексов может быть выполнено намного быстрее в чистом Python, занимая время, пропорциональное len(a) плюс len(b) плюс количество конфликтов, а не вложенные циклы, которые занимают время, пропорциональное произведению длин векторов:

def conflicts(a, b):
    from collections import defaultdict
    elt2ix = defaultdict(list)
    for i, elt in enumerate(a):
        elt2ix[elt].append(i)
    for j, elt in enumerate(b):
        if elt in elt2ix:
            for i in elt2ix[elt]:
                yield i, j

Тогда, например,

for pair in conflicts([1, 2, 4, 5, 2], [2, 3, 8, 4]):
    print(pair)

отображает

(1, 0)
(4, 0)
(2, 3)

который - индексы совпадающих вхождений 2 и 4.

Answer 2

• Я бы использовал pandas, который находится на numpy, для создания логической маски
• Требуется 4 строки кода

import numpy as np
import pandas as pd

# create test data
np.random.seed(1)
a = np.random.randint(10, size=(10, 1))
np.random.seed(1)
b = np.random.randint(8, 15, size=(10, 1))

# create dataframe
df_a = pd.DataFrame(a)
df_b = pd.DataFrame(b)

# find unique values in df_a
unique_a = df_a[0].unique().tolist()

# create a Boolean mask and return only values of df_b not found in df_a
values_not_in_a = df_b[~df_b[0].isin(unique_a)].to_numpy()

Значения

a = array([[5],
           [8],
           [9],
           [5],
           [0],
           [0],
           [1],
           [7],
           [6],
           [9]])

b = array([[13],
           [11],
           [12],
           [ 8],
           [ 9],
           [11],
           [13],
           [ 8],
           [ 8],
           [ 9]])

# final output array
values_not_in_a = array([[13],
                         [11],
                         [12],
                         [11],
                         [13]])

Только с использованием numpy

import numpy

# create test data
np.random.seed(1)
a = np.random.randint(10, size=(10, 1))
np.random.seed(1)
b = np.random.randint(8, 15, size=(10, 1))

ua = np.unique(a)  # unique values of a
ub = np.unique(b)  # unique values of b

mask_b = np.isin(b, ua, invert=True)
mask_a = np.isin(a, ub, invert=True)

b_values_not_in_a = b[mask_b]
a_values_not_in_b = a[mask_a]

# b_values_not_in_a
array([13, 11, 12, 11, 13])

# a_values_not_in_b
array([5, 5, 0, 0, 1, 7, 6])

timeit

# using the following arrays
np.random.seed(1)
a = np.random.randint(10, size=(90000, 1))
np.random.seed(1)
b = np.random.randint(8, 15, size=(120000, 1))

%%timeit
5.6 ms ± 151 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 3

Как предложил @Prune, вот решение, которое использует set s:

overlap = np.array(list(set(arr1) & set(arr2)))  # Depending on array shapes you may need to flatten or slice first
arr1 = arr1[~np.isin(arr1, overlap)]
arr2 = arr2[~np.isin(arr2, overlap)]

Answer 4

Пожалуйста, прочтите несколько руководств по векторным возможностям NumPy, а также по операторам включения последовательности Python. Вы пытаетесь запрограммировать крупномасштабное приложение, которому крайне необходимы языковые средства, которые вы еще не изучили.

Тем не менее, возможно, самый быстрый способ сделать это - преобразовать каждое в set и взять установить пересечение. Используемые операции: O (n) для последовательности / набора N элементов; ваш вложенный l oop равен O (N * M) (для двух размеров последовательности).

Любое руководство по наборам Python проведет вас через это.