两个非常大的列表之间查找重叠部分的最快算法是什么？

Question

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

我有一个列表，包含约70,000个格式为 <"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. 我可以创建任何中间结构。我正在尝试使用 shelve 构建一个倒排索引。

- rogueleaderr

---

你可以在磁盘上构造中间结构吗？看起来你可以从“反向索引”中受益，例如 {'A': [('A', B', 'C), ('A', 'X', 'Y')], ...}。 - spinlok

请明确一下，每个阶段匹配条目的确切标准是什么？ <A> <B> <C> 是否都必须匹配？还是只需要匹配 <A>、<B> 或 <C> 中的一个即可？另外，您的第二个过滤阶段也有点模糊。这里可以提供一些示例数据吗？ - Li-aung Yip

你应该提供第一个列表包含的简略示例，以及你希望结果列表包含的内容。 - Joel Cornett

数据是什么？数字？字符串？ - user545424

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)

- happydave

---

非常好的建议。这将很可能更快，因为在实现良好的set(使用散列键)中查找是O(1)时间，而不是在列表中搜索需要O(n)时间。 - Li-aung Yip

请注意，这段代码（和原帖中的代码一样）如果有多个匹配项，将会多次添加“line”，这可能不是期望的结果（我不确定需要什么样的过滤）。可以通过在“bucket.append(line)”之后添加“break”来轻松避免这种情况。 - Danica

我同意 - 我也不是很清楚 OP 到底想要什么。主要建议是使用集合来将运行时间减少约 70,000 倍。 - happydave

尽管小列表中的项目已经是唯一的，但使用set()确实会更快。我认为最终我会选择构建一个倒排索引，因为它可以轻松地完成第二步，即查找包含与第一次匹配的三元组中任何一个项目的三元组。构建索引需要相当长的时间，但一旦构建完成，查找速度非常快。 - rogueleaderr

@rogueleaderr：在这里，我们使用set，不是因为其中的元素保证是唯一的，这只是set的一个属性，而是因为在其中进行查找要快得多。（这是可能的，因为每个元素只能出现一次。） - Li-aung Yip