73

Python で大きな (10^7 ノード) グラフを操作できるようにする必要があります。各ノード/エッジに対応するデータは最小限です。たとえば、少数の文字列です。メモリと速度の点で、これを行う最も効率的な方法は何ですか?

dict の dict はより柔軟で実装が簡単ですが、リストのリストの方が高速であると直感的に期待しています。リストオプションでは、データを構造とは別に保持する必要もありますが、辞書では次のようなものが許可されます。

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

何を提案しますか？

はい、効率の意味をもう少し明確にする必要がありました。この特定のケースでは、ランダムアクセス検索の観点からそれを意味します。

データをメモリにロードすることは大きな問題ではありません。それは一度だけ行われます。時間のかかる部分は、ノードにアクセスすることです。そのため、情報を抽出して、関心のあるメトリックを測定できます。

各ノードをクラスにすることは考えていませんでした (プロパティはすべてのノードで同じです)。私は、誰かが共有できる同様のケースで直接の経験を持っていることを望んでいました. 結局のところ、グラフは CS で最も一般的な抽象化の 1 つです。

4

7 に答える 7

56

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)

視覚化も簡単です。

ここに画像の説明を入力

その他の視覚化: http://jonschull.blogspot.com/2008/08/graph-visualization.html

于 2008-08-26T17:43:06.413 に答える
13

この質問はかなり古いものですが、グラフ操作用の独自の python モジュールであるgraph-toolについて言及する価値があると思います。データ構造とアルゴリズムは C++ で実装されており、テンプレート メタプログラミングと Boost Graph ライブラリを使用しているため、非常に効率的です。したがって、そのパフォーマンス (メモリ使用量とランタイムの両方) は純粋な C++ ライブラリに匹敵し、使いやすさを犠牲にすることなく、典型的な Python コードよりも桁違いに優れています。私自身、非常に大きなグラフを扱うために常に使用しています。

于 2010-11-27T14:10:33.897 に答える
6

すでに述べたように、NetworkXは非常に優れており、別のオプションはigraphです。両方のモジュールには、必要になる可能性のあるほとんどの（すべてではないにしても）分析ツールがあり、両方のライブラリは大規模なネットワークで日常的に使用されています。

于 2008-08-27T10:01:21.803 に答える
4

実際の実装によっては、ディクショナリにもオーバーヘッドが含まれる場合があります。ハッシュテーブルには通常、使用可能なノードの素数が最初から含まれていますが、使用するノードは数個しかない場合があります。

あなたの例「プロパティ」から判断すると、最終レベルと実際のプロパティのクラスアプローチの方が良いでしょうか? または、プロパティの名前がノードごとに大きく変わっていますか?

「効率的」が何を意味するかは、次のような多くのことに依存すると思います。

  • 更新速度 (挿入、更新、削除)
  • ランダム アクセス検索の速度
  • 順次検索の速度
  • 使用メモリ

一般に、高速なデータ構造は、低速なデータ構造よりも多くのメモリを消費することがわかると思います。これは常に当てはまるわけではありませんが、ほとんどのデータ構造はこれに従っているようです。

ディクショナリは使いやすく、比較的均一に高速なアクセスを提供する可能性があります。おそらく、リストよりも多くのメモリを使用します。ただし、リストは一般に、データを挿入するときに、より多くのメモリを使用する X ノードを事前に割り当てない限り、より多くのオーバーヘッドを含む傾向があります。

一般的には、自分にとって最も自然と思われる方法を使用してから、システムの「ストレス テスト」を行い、かなりの量のデータをシステムに追加して、それが問題になるかどうかを確認することをお勧めします。

また、後で内部データ構造を変更する必要が生じた場合にプログラミング インターフェイスを変更する必要がないように、システムに抽象化レイヤーを追加することを検討することもできます。

于 2008-08-04T12:09:55.830 に答える
3

私が理解しているように、ランダムアクセスはPythonのdictとリストの両方で一定時間内にありますが、違いは、リストを使用した整数インデックスのランダムアクセスしか実行できないことです。ラベルでノードを検索する必要があると想定しているので、dictのdictが必要です。

ただし、パフォーマンスの面では、メモリへのロードは問題にならない可能性がありますが、使用量が多すぎると、ディスクにスワップすることになり、Pythonの非常に効率的なdictのパフォーマンスさえも低下します。メモリ使用量を可能な限り抑えるようにしてください。また、RAMは現在驚くほど安価です。このようなことをたくさんするなら、少なくとも4GBを持たない理由はありません。

メモリ使用量を抑えるためのアドバイスが必要な場合は、各ノードで追跡している情報の種類に関する詳細情報を提供してください。

于 2008-08-06T05:37:33.607 に答える
2

クラスベースの構造を作成すると、dictベースの構造よりもオーバーヘッドが大きくなる可能性があります。これは、Pythonでは、クラスが実装されるときに実際にdictを使用するためです。

于 2008-08-04T12:41:15.767 に答える
1

間違いなく NetworkX は、今までグラフに最適なデータ構造です。ヘルパー関数、データ構造とアルゴリズム、ランダム シーケンス ジェネレーター、デコレーター、カットヒル マッキー順序付け、コンテキスト マネージャーなどのユーティリティが付属しています。

NetworkX は、グラフ、ダイグラフ、およびマルチグラフに対応しているため、優れています。複数の方法でグラフを作成できます: 隣接リスト、複数行隣接リスト、エッジ リスト、GEXF、GML。Pickle、GraphML、JSON、SparseGraph6 などで動作します。

近似、二部、境界、中心性、クリーク、クラスタリング、カラーリング、コンポーネント、接続性、サイクル、有向非巡回グラフ、距離測定、支配集合、オイラー、同型、リンク分析、リンク予測、マッチングなど、さまざまな radimade アルゴリズムの実装があります。 、最小スパニング ツリー、リッチ クラブ、最短パス、トラバーサル、ツリー。

于 2016-01-18T09:08:03.070 に答える