python - 根据第三个列表过滤列表列表的最快方法？

Question

我有一个列表A，如下所示:

A = np.array([[1,2] ,
              [2,4] ,
              [3,4] , 
              [4,5] , 
              [6,7]]) 

并且我需要删除包含第三个列表 B 中任何元素的所有子列表。

例如，如果:

B = [1,2,5]

预期的结果是:

np.array([[3,4] ,
          [6,7]]) 

A的长度高达1,500,000，B也经常是几万个元素，所以性能很关键。 A 的子列表的长度始终为 2。

Answer 1

此处介绍的所有方法均基于 numpys boolean indexing .该方法是识别匹配项(独立于行)，然后沿行使用缩减(np.any 或 np.all)来查看应消除哪些行以及应保留哪些行。最后，将此掩码应用于您的数组 A 以仅获取有效行。这两种方法之间唯一真正的区别在于创建掩码的方式。

方法一:

如果预先知道 B 的值，您通常会使用 |(或运算符)链式比较。

a[~np.any(((a == 1) | (a == 2) | (a == 5)), axis=1)]

我将逐步完成此操作:

1. 寻找匹配项

   >>> ((a == 1) | (a == 2) | (a == 5))
   array([[ True,  True],
          [ True, False],
          [False, False],
          [False,  True],
          [False, False]], dtype=bool)
   

2. 检查每一行是否有一个True:

   >>> np.any(((a == 1) | (a == 2) | (a == 5)), axis=1)
   array([ True,  True, False,  True, False], dtype=bool)
   

3. 反转它:

   >>> ~np.any(((a == 1) | (a == 2) | (a == 5)), axis=1)
   array([False, False,  True, False,  True], dtype=bool)
   

4. 使用 bool 索引:

   >>> a[~np.any(((a == 1) | (a == 2) | (a == 5)), axis=1)]
   array([[3, 4],
          [6, 7]])
   

方法二:

代替这些 a == 1 |一个 == 2 | ... 你也可以使用 np.in1d :

>>> np.in1d(a, [1, 2, 5]).reshape(a.shape)
array([[ True,  True],
       [ True, False],
       [False, False],
       [False,  True],
       [False, False]], dtype=bool)

然后使用与上面基本相同的方法

>>> a[~np.any(np.in1d(a, [1, 2, 5]).reshape(a.shape), axis=1)]
array([[3, 4],
       [6, 7]])

方法 3:

如果 b 已排序，您还可以使用 np.searchsorted创建面具:

>>> np.searchsorted([1, 2, 5], a, side='left') == np.searchsorted([1, 2, 5], a, side='right')
array([[False, False],
       [False,  True],
       [ True,  True],
       [ True, False],
       [ True,  True]], dtype=bool)

这次您需要检查到达行中的所有值是否为True:

>>> b = [1, 2, 5]
>>> a[np.all(np.searchsorted(b, a, side='left') == np.searchsorted(b, a, side='right'), axis=1)]
array([[3, 4],
       [6, 7]])

时间:

第一种方法并不完全适合任意 B，因此我没有将其包含在这些时间安排中。

import numpy as np

def setapproach(A, B):  # author: Max Chrétien
    B = set(B)
    indices_to_del = [i for i, sublist in enumerate(A) if B & set(sublist)]
    C = np.delete(A, indices_to_del, 0)
    return C

def setapproach2(A, B):  # author: Max Chrétien & Ev. Kounis
    B = set(B)
    return np.array([sublist for sublist in A if not B & set(sublist)])

def isinapproach(a, b):
    return a[~np.any(np.in1d(a, b).reshape(a.shape), axis=1)]

def searchsortedapproach(a, b):
    b.sort()
    return a[np.all(np.searchsorted(b, a, side='left') == np.searchsorted(b, a, side='right'), axis=1)]

A = np.random.randint(0, 10000, (100000, 2))
B = np.random.randint(0, 10000, 2000)

%timeit setapproach(A, B)
# 929 ms ± 16.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit setapproach2(A, B)
# 1.04 s ± 13.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit isinapproach(A, B)
# 59.1 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit searchsortedapproach(A, B)
# 56.1 ms ± 1.05 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

然而，时间取决于值的范围，如果 B 已经排序并且 A、B 的长度。但是 numpy 接近接缝的速度比 set-solutions 快近 20 倍。然而，差异主要是因为使用 python 循环对 numpy 数组进行迭代非常低效，所以我将首先将 A 和 B 转换为 list :

def setapproach_updated(A, B):
    B = set(B)
    indices_to_del = [i for i, sublist in enumerate(A.tolist()) if B & set(sublist)]
    C = np.delete(A, indices_to_del, 0)
    return C

def setapproach2_updated(A, B):
    B = set(B)
    return np.array([sublist for sublist in A.tolist() if not B & set(sublist)])

这可能看起来很奇怪，但让我们重新计算时间:

%timeit setapproach_updated(A, B)
# 300 ms ± 2.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit setapproach2_updated(A, B)
# 378 ms ± 10.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这比普通循环快得多，只是先用 tolist 转换它，但仍然比 numpy 方法慢 5 倍以上。

所以请记住:当您必须在 NumPy 数组上使用基于 Python 的方法时，请检查先将其转换为列表是否更快!

让我们看看它在更大的阵列上的表现如何(这些尺寸与您问题中提到的尺寸相近):

A = np.random.randint(0, 10000000, (1500000, 2))
B = np.random.randint(0, 10000000, 50000)

%timeit setapproach_updated(A, B)
# 4.14 s ± 66.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit setapproach2_updated(A, B)
# 6.33 s ± 95.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit isinapproach(A, B)
# 2.39 s ± 102 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit searchsortedapproach(A, B)
# 1.34 s ± 21.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

差异越来越小，searchsorted 方法无疑胜出。

方法 4:

我还没说完呢!让我给你一个惊喜 numba ，它不是一个轻量级包但是非常强大如果它支持您需要的类型和功能:

import numba as nb

@nb.njit                # the magic is this decorator
def numba_approach(A, B):
    Bset = set(B)
    mask = np.ones(A.shape[0], dtype=nb.bool_)
    for idx in range(A.shape[0]):
        for item in A[idx]:
            if item in Bset:
                mask[idx] = False
                break
    return A[mask]

让我们看看它的表现如何:

A = np.random.randint(0, 10000, (100000, 2))
B = np.random.randint(0, 10000, 2000)

numba_approach(A, B)   # numba needs a warmup run because it's just-in-time compiling

%timeit numba_approach(A, B)
# 6.12 ms ± 145 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# This is 10 times faster than the fastest other approach!

A = np.random.randint(0, 10000000, (1500000, 2))
B = np.random.randint(0, 10000000, 50000)

%timeit numba_approach(A, B)
# 286 ms ± 16.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# This is still 4 times faster than the fastest other approach!

因此，您可以使其速度再快一个数量级。 Numba 不支持所有的 python/numpy 功能(并且并非所有功能都更快)，但在这种情况下就足够了!