加速嵌套循环比较

Question

我有两个数组arr1和arr2，大小分别为(90000,1)和(120000,1)。我想知道arr1的axis=0的任何元素是否存在于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元素，并将其与arr2的每个元素进行详尽的比较。如果找到匹配项，则附加索引list_conflict，第一个元素为arr1位置，第二个元素为arr2。然后fault_index_pos和fault_index_neg被压缩到唯一的元素中，因为arr1的元素可能位于arr2的多个位置上，并且列表将具有循环位置。最后，通过将fault_index列表作为要删除的索引，使用np.delete删除匹配元素

我正在寻找一种更快的冲突比较方法，称之为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

请学习一些有关NumPy向量功能的教程，以及Python的序列包含运算符。您正在尝试编写一个大型应用程序，该应用程序非常需要您尚未学习的语言工具

这就是说，也许最快的方法是将每个转换为set并取集合的交点。对于一个序列/一组n元素，所涉及的操作是O（n）；嵌套循环是O（N*M）（在两个序列大小上）

任何关于Python集的教程都将引导您完成这一过程

Answer 3

• 我会使用坐在numpy上的pandas创建一个布尔掩码
• 需要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)