基于第三个列表，过滤列表的列表的最快方法是什么？

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的长度达到了1500000，B中的元素数量通常也在数万个左右，因此性能至关重要。A的子列表长度始终为2。

- KMoore

---

a的子列表有多大？例如，len(a[123])是多少？它比b大还是小？ - Ma0

在这个例子中，b = [1, 2, 5] 吗？ - Ma0

是的，抱歉之前表达不够清晰，正在修改中。a的子列表总是由2个值组成。 - KMoore

Answer 1

所有这里提出的方法都基于numpy布尔索引。该方法是先识别匹配项（与行无关），然后沿着行使用缩减函数（np.any或np.all）来确定哪些行应该被消除，哪些应该被保留。最后，将此掩码应用于您的数组A，以仅获取有效行。这些方法之间唯一的区别在于如何创建掩码。

方法1：

如果事先已知B的值，则通常使用|（或运算符）链接比较。

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

我会逐步进行：

1. Finding matches

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

2. Check each row for one True:

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

3. Invert it:

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

4. Use boolean indexing:

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

方法二：

不使用 a == 1 | a == 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]])

方法三：

如果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方法似乎比集合解决方案快近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”方法明显更胜一筹。

第四种方法：

我还没有完成！让我用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功能（并非所有功能都更快），但在这种情况下足够了！

- MSeifert

---

我有一种感觉，[1, 2, 5] 是 b，它有 成千上万个元素，所以... - Ma0

我添加了 in1d 和 searchsorted 方法，这可以更好地适应长的 b。 - MSeifert

@KMoore同意！谢谢大家，有这样详细的答案真是太好了。 - Kruupös

Answer 2

使用set - 交集来重新创建一个新的索引列表，其中[1, 2, 5]在你的子列表中。 然后使用要删除的索引列表，使用numpy中集成的np.delete()函数。

import numpy as np

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

B = set([1, 2, 5])

indices_to_del = [i for i, sublist in enumerate(A) if B & set(sublist)]

C = np.delete(A, indices_to_del, 0)

print C
#[[3 4]
# [6 7]]

编辑

感谢@MSeifert，我得以改进我的答案。

@Ev.Kounis提出了另一种类似但更快的解决方案：

D = np.array([sublist for sublist in A if not B & set(sublist)])

- Kruupös

---

如果你在推导式之前只执行一次set(B)，那么你的方法就不会太糟糕。 - MSeifert

你可以使用完全相同的逻辑加上一个取反条件，而不是存储索引再删除它们。这样做的方式是：C = np.array([sublist for sublist in A if not B & set(sublist)])。如果“子列表”与“B”的交集为空集，则将“子列表”存储到np.array中。 - Ma0

谢谢大家的帮助。@Ev.Kounis 如果你想把我的最后一个解决方案作为你自己的发布，我可以删除它！我也会享受一下基准测试！ - Kruupös

@MaxChrétien 没问题，伙计。如果我有时间的话，我可能会自己测试一下 time。xD - Ma0

@Ev.Kounis 我已经测量了时间并将其添加到我的答案中。 :) - MSeifert