关于性能：Python中最有效的图形数据结构是什么？

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

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

你有什么建议？

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

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

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

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

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

可视化也很简单：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

它隐含了各种辐射算法，包括：
近似，二分法，边界，中心度，派系，聚类，着色，组件，连通性，循环，有向无环图，
距离度量，支配集，欧拉，同构，链接分析，链接预测，匹配，最小生成树，富俱乐部，最短路径，遍历，树。