6

我正在尝试在 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. 我可以创建任何我想要的中间结构。我现在正在尝试使用搁架构建的倒排索引。

4

1 回答 1

5

您可能应该首先将小列表存储在一个集合中，这样查找速度会更快。这可以防止对 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)
于 2012-05-03T02:37:11.857 回答