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

gomnis 发布于 2018-02-06 performance 最后更新 2018-02-06 01:05 2398 浏览

我需要能够操纵python中的大型(10 ^ 7节点)图。对应于每个节点/边的数据是最小的,比如少量的字符串。在记忆和速度 方面,最有效的方法是什么? 字典的字典是更灵活和更简单的实施,但我直观地期望列表的速度更快。列表选项还要求我将数据与结构保持分开,而字典将允许某种类型的数据:

graph[I][J]["Property"]="value"
你会建议什么?
是的,我应该更清楚我的意思是效率。在这个特定的情况下,我的意思是随机访问检索。 将数据加载到内存不是一个大问题。这一劳永逸。耗时的部分是访问节点,所以我可以提取信息,并衡量我感兴趣的指标。 我没有考虑让每个节点都是一个类(所有节点的属性都是相同的),但是似乎会增加额外的开销。我希望有人会有类似的情况下直接经验,他们可以分享。毕竟,图是CS中最常见的抽象之一。
已邀请:

oad

赞同来自:

字典也可能包含开销,取决于实际的实现。散列表通常包含一些可用节点的素数,即使您只能使用几个节点。 从你的例子来看,“财产”,你会更好的最后一级和真正的属性阶级方法?或者是属性名称从节点到节点的变化很大? 我想说,“高效”的意思取决于很多事情,比如:

  • 更新速度(插入,更新,删除)
  • 随机存取检索速度
  • 顺序检索的速度
  • 使用的内存
  • 我认为你会发现一个快速的数据结构通常会消耗更多的内存。情况并非总是如此,但是大多数数据结构似乎都是这样的。 字典可能易于使用,并给你相对一致的快速访问,它将最有可能使用更多的内存比,如你所建议的,列表。但是,列表通常在向其中插入数据时往往会包含更多的开销,除非它们预先分配X节点,在这些节点中它们将再次使用更多的内存。 一般来说,我的建议是只使用最自然的方法,然后对系统进行“压力测试”,向其添加大量的数据,看看是否成为问题。 您也可以考虑在系统中添加一个抽象层,以便稍后需要更改内部数据结构时不必更改编程接口。

vvelit

赞同来自:

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

mnatus

赞同来自:

据我了解,Python的字典和列表都是随机访问,不同的是,你只能随意访问整数索引和列表。我假设你需要通过标签查找节点,所以你需要一个字典的字典。 然而,在性能方面,将其加载到内存中可能不成问题,但如果使用太多,则最终会交换到磁盘,甚至会导致Python高效的字典性能下降。尽量保持内存使用率下降。另外,RAM现在非常便宜;如果你做这种事情很多,没有理由不少于4GB。 如果您需要关于减少内存使用量的建议,请提供有关您要跟踪的每个节点的信息种类的更多信息。

qui_id

赞同来自:

我强烈建议你看看NetworkX。这是一个经过考验的战争战争,也是大多数“研究”类型需要分析基于网络的数据的第一个工具。我已经在笔记本上操作了数百个边缘的图形,没有问题。其功能丰富,非常易于使用。你会发现自己更关注手头的问题,而不是基础实施的细节。 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)
可视化也很简单: enter image description here 更多可视化:http://jonschull.blogspot.com/2008/08/graph-visualization.html

eipsum

赞同来自:

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

miste

赞同来自:

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

jculpa

赞同来自:

毫无疑问,到目前为止,NetworkX是最好的数据结构。它带有像Helper函数,数据结构和算法,随机序列生成器,装饰器,Cuthill-Mckee排序,上下文管理器 NetworkX是伟大的,因为它的图形,二联图和多图形。它可以用多种方式编写图形:邻接列表,多行邻接列表, 边缘列表,GEXF,GML。它适用于Pickle,GraphML,JSON,SparseGraph6等 它有各种radimade算法implimentation包括: 逼近,第二部分,边界,中心性,派系,聚类,着色,组件,连通性,周期,定向非循环图, 距离测度,控制集,欧拉,同构,链接分析,链接预测,匹配,最小生成树,Rich Club,最短路径,遍历,树