如何删除一个列表中的子列表（即子列表），如果该子列表中的任何元素在另一个列表中？

Question

我有一个包含多个子列表的列表。例如：

full_list = [[1, 1, 3, 4], [3, 99, 5, 2],[2, 4, 4], [3, 4, 5, 2, 60]]

我还有另一个列表，名为“omit”。例如：

omit = [99, 60, 98]

我希望移除full_list中的子列表，如果该子列表中的任何元素在省略列表中。例如，我希望得到的列表是：

reduced_list = [[1, 1, 3, 4], [2, 4, 4]]

因为只有这些子列表中没有在省略列表中的元素。

我猜想可以通过列表推导式轻松解决，但我无法做到。我尝试了很多方法，例如：

reduced_list = [sublist for sublist in full_list if item for sublist not in omit] 

• 这段代码出现了错误（语法无效），但我认为不仅仅是这个问题。

非常感谢任何帮助！

附言，上述问题是一个简化版。我的最终目标是从一个非常长的字符串列表中（例如，500,000个子列表）删除子列表，如果这些子列表中的任何元素（一个字符串）在一个包含超过2000个字符串的“省略”列表中，则删除。

- ansonw

---

你们太棒了！感谢你们的回复。在更长的列表上，它表现得像魔术一样。 - ansonw

Answer 1

使用set和all()：

>>> omit = {99, 60, 98}
>>> full_list = [[1, 1, 3, 4], [3, 99, 5, 2],[2, 4, 4], [3, 4, 5, 2, 60]]
>>> [item for item in full_list if all(x not in omit for x in item)]
[[1, 1, 3, 4], [2, 4, 4]]

这种方法与@alecxe（或@Óscar López）的解决方案的主要区别在于它完全避免了创建任何集合或列表，并且可以实现全部短路。而set-intersection返回一个包含所有与omit集合共同项的新集合，通过检查其长度来确定是否有任何公共项。（set-intersection在C速度下内部处理，因此比all中使用的常规Python循环更快。）

时间比较：

>>> import random

无交集项目：

>>> omit = set(random.randrange(1, 10**18) for _ in xrange(100000))
>>> full_list = [[random.randrange(10**19, 10**100) for _ in xrange(100)] for _ in xrange(1000)]

>>> %timeit [item for item in full_list if not omit & set(item)]
10 loops, best of 3: 43.3 ms per loop
>>> %timeit [x for x in full_list if not omit.intersection(x)]
10 loops, best of 3: 28 ms per loop
>>> %timeit [item for item in full_list if all(x not in omit for x in item)]
10 loops, best of 3: 65.3 ms per loop

所有项相交：

>>> full_list = [range(10**3) for _ in xrange(1000)]
>>> omit = set(xrange(10**3))
>>> %timeit [item for item in full_list if not omit & set(item)]
1 loops, best of 3: 148 ms per loop
>>> %timeit [x for x in full_list if not omit.intersection(x)]
1 loops, best of 3: 108 ms per loop
>>> %timeit [item for item in full_list if all(x not in omit for x in item)]
100 loops, best of 3: 1.62 ms per loop

一些项目存在交集：

>>> omit = set(xrange(1000, 10000))
>>> full_list = [range(2000) for _ in xrange(1000)]
>>> %timeit [item for item in full_list if not omit & set(item)]
1 loops, best of 3: 282 ms per loop
>>> %timeit [x for x in full_list if not omit.intersection(x)]
1 loops, best of 3: 159 ms per loop
>>> %timeit [item for item in full_list if all(x not in omit for x in item)]
1 loops, best of 3: 227 ms per loop

- Ashwini Chaudhary

---

既然您已经在使用集合，那么使用本地的集合操作会更好、更快。 - Anorov

@Anorov 我可以这样做，但是仅为了检查长度而在内存中创建一个集合是没有意义的。 - Ashwini Chaudhary

Answer 2

试试这个：

full_list = [[1, 1, 3, 4], [3, 99, 5, 2], [2, 4, 4], [3, 4, 5, 2, 60]]
omit = frozenset([99, 60, 98])
reduced_list = [x for x in full_list if not omit.intersection(x)]

我对输入数据唯一的更改是将omit设置为一个集合，出于效率原因，因为它允许我们执行快速交集（它被冻结，因为我们不会修改它），注意x不必是一个集合。现在reduced_list变量将包含预期值：

reduced_list
=> [[1, 1, 3, 4], [2, 4, 4]]

- Óscar López

---

最好将 omit 作为一个集合放在循环内部转换的过程中，而不是每次迭代都进行转换。 - Anorov

@Anorov 在您之前 :) - Óscar López

对于frozenset，加1会快一些（请查看我的回答中的迷你基准测试）。 - alecxe

Answer 3

将omit设置为一个集合，在每次迭代时检查是否有交集：

>>> full_list = [[1, 1, 3, 4], [3, 99, 5, 2],[2, 4, 4], [3, 4, 5, 2, 60]]
>>> omit = [99, 60, 98]
>>> omit = set(omit)  # or just omit = {99, 60, 98} for python >= 2.7
>>> [item for item in full_list if not omit & set(item)]
[[1, 1, 3, 4], [2, 4, 4]]

建议使用 frozenset 而不是像 @Óscar López 建议的使用 set。使用 frozenset 可以使程序运行更快:

import timeit


def omit_it(full_list, omit):
    return [item for item in full_list if not omit & set(item)]

print timeit.Timer('omit_it([[1, 1, 3, 4], [3, 99, 5, 2],[2, 4, 4], [3, 4, 5, 2, 60]], {99, 60, 98})',
                   'from __main__ import omit_it').timeit(10000)

print timeit.Timer('omit_it([[1, 1, 3, 4], [3, 99, 5, 2],[2, 4, 4], [3, 4, 5, 2, 60]], frozenset([99, 60, 98]))',
                   'from __main__ import omit_it').timeit(10000)

打印：

0.0334849357605
0.0319349765778

- alecxe

---

我本来想使用 any() 来发布一个解决方案，但我认为这个更好，更符合 Python 风格。 - Anorov

注意，omit & set(item) 不会短路并且会在内存中创建一个新的set。 - Ashwini Chaudhary

@AshwiniChaudhary 是的，实际上看到什么更快确实很有趣..当然这取决于输入。 - alecxe

@AshwiniChaudhary 这是一个很好的观点，但由于实现的原因，即使考虑到从all()短路，set.intersection()可能会更快。看到基准测试将是有趣的。 - Anorov

顺便说一下，你可以使用：not omit.intersection(item)，这比not omit & set(item)更快。 - Ashwini Chaudhary