什么是Python中最高效的graphics数据结构?

我需要能够操纵python中的大型(10 ^ 7节点)图。 对应于每个节点/边的数据是最小的,比如less量的string。 在内存和速度方面,最有效率的方式是什么?

字典的字典是更灵活和更简单的实施,但我直观地期望列表的速度更快。 列表选项还要求我将数据与结构保持分开,而字典将允许某种types的数据:

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

你会build议什么?


是的,我应该更清楚我的意思是效率。 在这个特定的情况下,我的意思是随机访问检索。

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

我没有考虑让每个节点都是一个类(所有节点的属性都是相同的),但是似乎会增加额外的开销。 我希望有人会有类似的情况下直接经验,他们可以分享。 毕竟,图是CS中最常见的抽象之一。

我强烈build议你看看NetworkX 。 这是一个经过考验的战争战争,也是大多数“研究”types需要分析基于networking的数据的第一个工具。 我已经在笔记本上操作了数百个边缘的graphics,没有问题。 其function丰富,非常易于使用。 你会发现自己更关注手头的问题,而不是基础实施的细节。

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 (hagberg@lanl.gov)""" __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) 

可视化也很简单:

在这里输入图像说明

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

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

如前所述,NetworkX非常好,另一种select是igraph 。 两个模块都将拥有大多数(如果不是全部的话)您可能需要的分析工具,并且这两个库都经常用于大型networking。

字典也可能包含开销,取决于实际的实现。 散列表通常包含一些可用节点的素数,即使您只能使用几个节点。

从你的例子来看,“财产”,你会更好的最后一级和真正的属性阶级方法? 或者是属性名称从节点到节点的变化很大?

我想说,“高效”的意思取决于很多事情,比如:

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

我认为你会发现一个快速的数据结构通常会消耗更多的内存。 情况并非总是如此,但是大多数数据结构似乎都是这样的。

字典可能易于使用,并给你相对一致的快速访问,它将最有可能使用更多的内存比,如你所build议的,列表。 但是,列表通常在向其中插入数据时往往会包含更多的开销,除非它们预先分配X节点,在这些节点中它们将再次使用更多的内存。

一般来说,我的build议是只使用最自然的方法,然后对系统进行“压力testing”,向其添加大量的数据,看看是否成为问题。

您也可以考虑在系统中添加一个抽象层,以便稍后需要更改内部数据结构时不必更改编程接口。

据我了解,Python的字典和列表都是随机访问,不同的是,你只能随意访问整数索引和列表。 我假设你需要通过标签查找节点,所以你需要一个字典的字典。

然而,在性能方面,将其加载到内存中可能不成问题,但如果使用太多,则最终会交换到磁盘,甚至会导致Python高效的字典性能下降。 尽量保持内存使用率下降。 另外,RAM现在非常便宜; 如果你做这种事情很多,没有理由不less于4GB。

如果您需要关于减less内存使用量的build议,请提供有关您要跟踪的每个节点的信息种类的更多信息。

构build一个基于类的结构可能会比基于字典的结构花费更多的开销,因为在python类实际使用时实际上使用了字典。

毫无疑问,到目前为止,NetworkX是最好的数据结构。 它带有像Helper函数,数据结构和algorithm,随机序列生成器,装饰器,Cuthill-Mckeesorting,上下文pipe理器

NetworkX是伟大的,因为它的graphics,二联图和多graphics。 它可以用多种方式编写graphics:邻接列表,多行邻接列表,边缘列表,GEXF,GML。 它适用于Pickle,GraphML,JSON,SparseGraph6等

它具有各种各样的radimadealgorithm,包括:近似,二分图,边界,中心性,派系,聚类,着色,组件,连通性,周期,有向无环图,距离测度,支配集,欧拉,同构,链接分析,链接预测,匹配,最小生成树,富有俱乐部,最短path,遍历,树。