如何快速检查一个列表是否存在于一个列表的列表中

Question

我有一个列表

a=[[1,2,3,4,5,6],[7,8,9,10,11,12]]   

如何快速检查列表 a 中的任何一个列表是否存在于另一个列表 b 中，其中

b=[[5, 9, 25, 31, 33, 36],[7,8,9,10,11,12],[10, 13, 22, 24, 33, 44]]

如果a中的任何一个列表存在于b中，我想要将其删除。我目前正在使用以下代码：

for each in a:
    for item in b:
        if set(each).issubset(item)
            a.remove(each)

这样做虽然可行，但处理大型列表时速度较慢，因此想知道是否有更好的方法。上面的代码给我以下结果：

print(a)
[[1, 2, 3, 4, 5, 6]]

我不担心顺序，例如，如果列表 a 是 [1,2,3,4,5,6]，只要在列表 b 中存在 [1,2,3,4,5,6] 或者 [3,4,1,6,2,5] 等等，就可以将其删除。

- West

---

如果 a 是 [[1, 1, 2, 3]]，而 b 是 [[7, 3, 2, 1], [4, 5, 6]]，那会怎么样？ - bipll

@bipll 这也是可以接受的。 - West

Answer 1

使用带有set的列表推导式。

例子：

```python unique_numbers = {x for x in numbers} ```

其中，`numbers`是一个包含重复元素的列表。

a=[[1,2,3,4,5,6],[7,8,9,10,11,12]]  
b=[[5, 9, 25, 31, 33, 36],[7,8,9,10,11,12],[10, 13, 22, 24, 33, 44]]

setA = set(map(tuple, a))
setB = set(map(tuple, b))

print([i for i in setA if i not in setB])

输出：

[(1, 2, 3, 4, 5, 6)]

- Rakesh

---

非常感谢，这肯定跑得更快了。在一个包含100万个项目的列表a和一个包含1646个项目的列表b上进行了测试，仅花费了1.9秒。我的解决方案需要很久才能完成。 - West

我认为这对于顺序不同的列表无效。 - emilys

Answer 2

使用set.difference可以实现一个功能性的解决方案:

res = set(map(tuple, a)).difference(set(map(tuple, b)))

[(1, 2, 3, 4, 5, 6)]

解释

1. 由于list不是可哈希的类型，我们将子列表转换为tuple类型，这些类型是不可变且可哈希的，例如set(map(tuple, a))。
2. 然后使用set.difference来计算两个结果集之间的差异。

- jpp

---

感谢您提供的解决方案，它绝对比我的更快，当在一个包含100万个项目的列表a和一个包含1646个项目的列表b上进行测试时，只需要大约5秒钟，但Rakesh的示例证明了速度更快。 - West

现在可以重新检查时间吗？我已经更新了代码，删除了“tuple”->“list”的转换。看起来这个耗时的部分对于你的使用情况并不必要。 - jpp

当然，它肯定有所改善，现在平均需要约2.2秒，好多了。谢谢。 - West

Answer 3

如果您不关心元素的顺序和频率，即将列表视为无序集合，则您的解决方案可能几乎是正确的（在迭代相同列表时删除元素可能不是最佳选择），但存在两个严重的次优性。

首先，您当前每个a元素都将b的元素转换为一组。我想知道Python编译器是否可以优化重复的工作，至少您可以尝试自己做。

接下来，您不需要错误地并且平方地删除元素，只需简单地过滤它们即可。

faster_b = [frozenset(x) for x in b]

def not_in_b(list):
    l = frozenset(list)
    for x in faster_b:
        if l <= x: return False
    return True

print(list(filter(not_in_b, a)))

这个可能更快。

$ python3
Python 3.6.5 (default, May 11 2018, 04:00:52) 
[GCC 8.1.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> a=[[1,2,3,4,5,6],[7,8,9,10,11,12]]
>>> b=[[5, 9, 25, 31, 33, 36],[7,8,9,10,11,12],[10, 13, 22, 24, 33, 44]]
>>> faster_b = [frozenset(x) for x in b]
>>> 
>>> def not_in_b(list):
...     l = frozenset(list)
...     for x in faster_b:
...         if l <= x: return False
...     return True
... 
>>> print(list(filter(not_in_b, a)))
[[1, 2, 3, 4, 5, 6]]
>>> a=[[1, 1, 2, 3]]
>>> b=[[7, 3, 2, 1], [4, 5, 6]]
>>> faster_b = [frozenset(x) for x in b]
>>> print(list(filter(not_in_b, a)))
[]
>>> a=[[1, 1, 2, 3], [42, 5, 6]]
>>> print(list(filter(not_in_b, a)))
[[42, 5, 6]]

- bipll

---

我在行 print(list(filter(a, not_in_b))) 中收到一条错误信息 TypeError：'function' object is not iterable。 - West

啊，显然是filter的参数顺序问题，看我的修改。 - bipll

由于您编辑的代码运行时间超过了2分钟并导致Python冻结，我不得不停止脚本的运行。 - West

@West 你可能复制错了什么。我已经编辑了我的帖子，并简要演示了它的工作原理。 - bipll