python - 从两个列表列表中查找共同元素

Question

我有两个列表列表，其中包含一些像这样的 3D 坐标(例如):

a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]
b[n] = [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]

查找“b”的任何元素是否在列表“a”中有任何坐标的快速方法是什么？例如，在给定的示例中，“a[2]”和“b[2][1]”是相同的，因此我希望程序返回“true”。

Answer 1

将 b 的最内层列表转换成一个集合(s)，然后遍历 a 以检查 中是否有任何项目>a 是否存在于 s 中。

tot_items_b = sum(1 for x in b for y in x) #total items in b

Sets 提供了一个O(1) 查找，所以整体复杂度将是:

O(max(len(a), tot_items_b))

def func(a, b):
   #sets can't contain mutable items, so convert lists to tuple while storing

   s = set(tuple(y) for x in b for y in x)
   #s is set([(41, 2, 34), (98, 23, 56), (42, 25, 64),...])

   return any(tuple(item) in s for item in a)

演示:

>>> a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
>>> b = [[[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]], [[11, 22, 3], [42, 25, 64], [43, 45, 23]], [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]]
>>> func(a,b)
True

关于任何的帮助:

>>> print any.__doc__
any(iterable) -> bool

Return True if bool(x) is True for any x in the iterable.
If the iterable is empty, return False.

使用集合交集获取所有公共(public)元素:

>>> s_b = set(tuple(y) for x in b for y in x)
>>> s_a = set(tuple(x) for x in a)
>>> s_a & s_b
set([(4, 5, 6)])