带索引的两个嵌套列表的Python并集

Question

我想要找出两个嵌套列表的并集，并且还想知道哪些值是共同的。

我有两个列表，比如说 A = [[1,2,3],[4,5,6],[7,8,9]] 和 B = [[1,2,3,4],[3,3,5,7]]，但是每个列表的长度大约有10万个。对于列表A，还有一个索引向量 I = [2,3,4]，它的长度和A一样。

我想要找出列表B中所有的子列表，这些子列表的前3个元素和A中的某个子列表相等。在这个例子中，我想得到 B[0]（也就是 [1,2,3,4]），因为它的前3个元素和 A[0] 相等。此外，我还想知道 A[0] 在索引向量I中的位置，也就是 I[0]。

我尝试了不同的方法，但到现在为止都没有成功 :(

首先我试了这个：

Common = []

for i in range(len(B)):

   if B[i][:3] in A:

      id = [I[x] for x,y in enumerate(A) if y == B[i][:3]][0]
         ctdCommon.append([int(id)] + B[i])   

但是这样做要花很长时间，或者根本就没有完成。

然后我把 A 和 B 转换成集合，并找出它们的并集，这样速度很快，但我不知道怎么得到对应的索引。

有没有人有什么好主意？

Answer 1

创建一个辅助字典（这个过程的工作量是 O(len(A)）——假设A中每个子列表的前三个项目能够唯一识别这个子列表（如果不能，就需要用字典来存储列表）：

aud = dict((tuple(a[:3]), i) for i, a in enumerate(A))

然后利用这个字典，对B进行一次循环（这个过程的工作量是 O(len(B))），以获取B中的子列表和A中的索引：

result = [(b, aud[tuple(b[:3])]) for b in B if tuple(b[:3]) in aud]