performance -Python中最有效的图形数据结构是什么?

Translate

我需要能够在python中处理大型(10 ^ 7个节点)图。对应于每个节点/边缘的数据是最少的,例如,少量的字符串。什么是最有效的内存和速度,这样做的方式?

dict的dict更灵活,更易于实现,但我直观地期望列表列表会更快。 list选项还要求我将数据与结构分开,而dict则允许某种形式:

graph[I][J]["Property"]="value"

你有什么建议?


是的,我应该对效率的含义更加清楚。在这种特殊情况下,我的意思是随机访问检索。

将数据加载到内存中并不是一个大问题。一劳永逸。耗时的部分是访问节点,因此我可以提取信息并衡量我感兴趣的指标。

我没有考虑过将每个节点都设为一个类(所有节点的属性都相同),但这似乎会增加额外的开销?我希望有人能对他们可以分享的类似案例有一些直接的经验。毕竟,图是CS中最常见的抽象之一。

This question and all comments follow the "Attribution Required."

所有的回答

Translate

我强烈建议你看看网络X。它是经过战斗考验的战马,是大多数“研究”类型需要进行基于网络的数据分析时才能使用的第一个工具。我已经在笔记本上毫无问题地操纵了具有成千上万条边的图形。它的功能丰富,非常易于使用。您会发现自己将更多的精力放在手头的问题上,而不是基础实现中的细节上。

例子Erdős-Rényi随机图的生成和分析


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg ([email protected])"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

可视化也很简单:

enter image description here

更多可视化:http://jonschull.blogspot.com/2008/08/graph-visualization.html

来源
Translate

尽管这个问题现在已经很老了,但我认为值得一提的是我自己的用于图操作的python模块,称为图形工具。这是非常有效的,因为数据结构和算法是使用Boost Graph Library通过C ++和模板元编程来实现的。因此,它的性能(在内存使用和运行时方面)都可以与纯C ++库相媲美,并且可以在不牺牲易用性的情况下比典型的python代码好几个数量级。我自己经常使用它来处理非常大的图形。

来源
Kai
Translate

如前所述,NetworkX非常好,另一种选择是。这两个模块都将具有您可能需要的大多数(如果不是全部)分析工具,并且这两个库通常与大型网络一起使用。

来源
Translate

字典也可能包含开销,具体取决于实际实现。哈希表通常包含一些可用节点开头的质数,即使您可能只使用几个节点。

以您的“属性”为例,对于最终级别和不动产,您是否可以使用类方法更好?还是属性的名称在节点之间变化很大?

我会说“有效”的意思取决于很多事情,例如:

  • 更新速度(插入,更新,删除)
  • 随机访问检索的速度
  • 顺序检索的速度
  • 使用的内存

我认为您会发现,快速的数据结构通常会比慢速的数据结构消耗更多的内存。并非总是如此,但是大多数数据结构似乎都遵循了这一点。

字典可能易于使用,并为您提供相对统一的快速访问,它最有可能比您建议的列表使用更多的内存。但是,列表通常会在您向其中插入数据时包含更多开销,除非它们预先分配了X节点,在X节点中它们将再次使用更多内存。

通常,我的建议是只使用对您来说似乎最自然的方法,然后对系统进行“压力测试”,向系统中添加大量数据,然后查看它是否成为问题。

您可能还会考虑在系统中添加抽象层,这样,如果以后需要更改内部数据结构时,就不必更改编程接口。

来源
Translate

据我了解,Python的字典和列表的访问都是在恒定的时间内进行的,不同之处在于您只能对带有列表的整数索引进行随机访问。我假设您需要按其标签查找节点,因此您需要一个字典。

但是,在性能方面,将其加载到内存中可能不是问题,但是如果使用过多,最终将交换到磁盘,这甚至会破坏Python高效指令的性能。尝试尽可能降低内存使用率。而且,RAM现在非常便宜。如果您经常执行此类操作,则没有理由不要至少拥有4GB。

如果您想降低内存使用量的建议,请提供更多有关每个节点要跟踪的信息类型的信息。

来源
Translate

制作基于类的结构可能比基于字典的结构具有更多的开销,因为在python中,类在实现时实际上会使用字典。

来源
Translate

毫无疑问,到目前为止,NetworkX是图形的最佳数据结构。它带有实用程序,例如帮助程序功能,数据结构和算法,随机序列生成器,装饰器,Cuthill-Mckee排序,上下文管理器

NetworkX之所以出色,是因为它非常适合图形,有向图和多重图。它可以通过多种方式编写图形:邻接表,多行邻接表,边列表,GEXF,GML。它与Pickle,GraphML,JSON,SparseGraph6等一起使用。

它具有各种辐射算法的实现,包括:逼近,二分,边界,中心性,集团,聚类,着色,组件,连通性,循环,有向无环图,距离度量,支配集,欧拉,同构,链接分析,链接预测,匹配,最小生成树,富俱乐部,最短路径,遍历,树。

来源
下一个问题:
开源Ruby项目