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

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\u列表中的每个项目进行70000次迭代。在

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