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

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

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

你有什么建议？

是的，我对效率的含义应该有所了解。在这种特殊情况下，我的意思是随机访问检索。

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

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

解决方案

回答

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

以"属性"为例，对于最终级别和不动产，我们是否可以使用类方法更好？还是属性的名称在节点之间变化很大？

我会说"有效"的意思取决于很多事情，例如：

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

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

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

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

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

回答

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

回答

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

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

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

回答

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

Erd？s-Rnyi随机图生成和分析的示例

"""
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)

可视化也很简单：

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

回答

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

回答

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