用于查找两个非常大的列表之间重叠的最快算法？

Question

我正在尝试用Python构建一个算法来过滤大块的RDF数据.

我有一个列表,包括大约7万个格式化的项目<"datum">.

然后,我有大约6GB的物品(三倍)格式化 <"A"> <"B"> <"C">

我想提取包含第一个列表中任何项目的所有三元组,然后从第一个提取中提取包含任何单个项目的任何三元组(净效果是形成图形的分区,该分区通过一步连接到种子从第一个列表).

我没有能够为此提出一个很好的算法(没有正确的CS训练,这没有帮助.)

到目前为止,我提出的最好的方法是首先将大列表中的三元组分成三个项目列表[<"A">, <"B">, <"C">].然后我将它分成块,并使用多处理创建进程,这些进程占用完整的小列表和大列表的一大块...

for line in big list:
    for item in small list:
      if item in line:
       bucket.append(line)

这个算法需要很长时间.

有没有更快的方法来做到这一点？如果有一个特定的算法,你可以给我一个名字,我会弄清楚如何实现它.

谢谢!

每条评论的澄清:

1. 所有数据项都是字符串.所以小列表可能包含["Mickey", "Mouse", "Minny", "Cat"],大列表可能是[["Mickey","Pluto","Bluto"],["John", "Jane", "Jim]...]

2. 每个大列表三元组中只有一个项目需要匹配小列表中的项目以进行计数

3. 小列表中的所有项目实际上都是唯一的,所以我认为无论如何都不会将它们转换为集合.但我会尝试.

4. 我可以创建我想要的任何中间结构.我正在尝试使用搁架构建的倒置索引.

Answer 1

您可能应该首先将小列表存储在一个集合中,因此查找速度更快.这可以防止对big_list中的每个项目进行70,000次迭代.

small_list_set = set(small_list)
for line in big_list:
    for item in line:
        if item in small_list_set:
            bucket.append(line)