将超大RDF三元组加载到iGraph中 -> 快速查找顶点的方法？

Question

我需要把DBPedia图的一部分加载到iGraph中，以便计算一些图的统计数据（比如节点的中心性等）。我使用Redlands的libRDF这个Python库来加载DBPedia的三元组。每个节点都有一个URI（唯一标识符）。

我在把图加载到iGraph时遇到了一些麻烦。我的操作步骤是这样的：

1) 读取一行三元组（主题、谓词、宾语）

2) 使用以下算法来获取或创建一个带属性的顶点

def add_or_find_vertex (self, g, uri):
    try:
        return g.vs.find(name=uri)
    except (KeyError, ValueError):
        g.add_vertex(name=uri)
        return g.vs.find(name=uri)

subjVertex = self.add_or_find_vertex(self.g, subject)
objVertex = self.add_or_find_vertex(self.g, object)
self.g.add_edge(subjVertex, objVertex, uri=predicate)

问题是我的脚本运行得非常慢，而我需要加载2500万条三元组。每个节点都是唯一的，但在三元组文件中会出现多次。因此，在创建边之前，我需要先查找一下。你能告诉我“find”方法是否使用了索引来进行查找（比如哈希表等）吗？顶点查找的复杂度是多少？你会怎么做呢？

非常感谢！

Answer 1

之前已经在这里回答过了。为了完整起见，我也把我的回答复制过来了：

查找顶点通常是O(|V|)的复杂度，因为顶点的属性默认是没有索引的——除了顶点的name属性，它是有索引的。不过，g.vs.find只有在你这样使用时才会利用这个索引：g.vs.find(url)，而如果你这样用：g.vs.find(name=url)，就不会使用索引。这算是一个小bug，因为在这两种情况下都可以使用索引。你也可以看看昨天的邮件讨论。

不过要注意，igraph的数据结构是为静态图优化的，所以g.add_vertex（我想你也在用g.add_edge）可能会成为瓶颈。igraph内部使用一个带索引的边列表来存储图，每次你修改图时都需要重建索引，所以在可能的情况下，批量添加顶点和边会更高效。

既然你似乎已经有一个迭代器，可以以(subject, predicate, object)的形式输出图的边，或许使用Graph.DictList一次性构建图会更简单，因为它也会处理顶点ID存储在name属性中，合理地批量添加边，并且还会从你的三元组中添加predicate属性：

>>> g = Graph.DictList(vertices=None, edges=({"source": subject,
...         "target": object, "predicate": predicate}
...         for subject, predicate, object in your_iterator))

Graph.DictList在我的机器上处理100000个预生成的随机三元组只用了1.63秒，所以我想这会稍微改善一下性能。