ما هو الأكثر كفاءة الرسم البياني بنية البيانات في الثعبان ؟ [مغلقة]

Question

أنا بحاجة إلى أن تكون قادرة على التعامل مع مجموعة كبيرة (10^7 العقد) الرسم البياني في بيثون.البيانات المقابلة لكل عقدة/edge هو الحد الأدنى ، يقول عدد قليل من السلاسل.ما هو الأكثر كفاءة من حيث الذاكرة وسرعة, طريقة لفعل هذا ؟

أ ديكت من dicts أكثر مرونة وبساطة التنفيذ ، لكن حدسي نتوقع قائمة من القوائم أن تكون أسرع.قائمة الخيار يتطلب أيضا أن أظل البيانات منفصلة عن الهيكل ، في حين dicts تسمح شيء من هذا القبيل:

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

ماذا تقترح ؟

---

نعم ، كان ينبغي أن يكون قليلا أكثر وضوحا على ما أعنيه من الكفاءة.في هذه الحالة تحديدا أعني من حيث الوصول العشوائي واسترجاعها.

تحميل البيانات في الذاكرة ليست مشكلة كبيرة.أن يتم ذلك مرة واحدة وإلى الأبد.الجزء تستغرق وقتا طويلا يزور العقد بحيث لا يمكن استخراج المعلومات و قياس مقاييس أنا مهتم في.

لم يعتبر مما يجعل كل عقدة فئة (الخصائص هي نفسها بالنسبة لجميع العقد) ولكن يبدو أن هذا من شأنه أن يضيف طبقة إضافية من النفقات العامة ؟ كنت أتمنى شخص ما من شأنه أن يكون لديك بعض الخبرة المباشرة مع قضية مماثلة يمكن تقاسمها.بعد كل شيء, الرسوم البيانية هي واحدة من الأكثر شيوعا تجريدات في CS.

Answer 1

وأود أن الدعوة بقوة نظرتم NetworkX.انها معركة اختبار حصان الحرب و أول أداة أكثر 'البحوث' أنواع متناول عندما تحتاج إلى القيام بتحليل الشبكة القائمة على البيانات.لدي التلاعب الرسوم البيانية مع 100s من الآلاف من الحواف من دون مشكلة على جهاز كمبيوتر محمول.ميزة الغنية وسهلة جدا للاستخدام.سوف تجد نفسك تركز أكثر على المشكلة في متناول اليد بدلا من التفاصيل في تنفيذ الأساسية.

مثال 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

Answer 2

على الرغم من أن هذا السؤال هو الآن قديمة جدا ، وأعتقد أنه من المفيد أن نذكر بلدي بيثون وحدة الرسم البياني التلاعب يسمى الرسم البياني-أداة.فمن فعالة جدا ، منذ هياكل البيانات والخوارزميات يتم تنفيذها في C++, مع قالب metaprograming باستخدام دفعة الرسم البياني المكتبة.ولذلك أدائها (سواء في استخدام الذاكرة وقت التشغيل) هي مماثلة نقية C++ المكتبة, و يمكن أن تكون أوامر من حجم أفضل من المعتاد كود بايثون ، دون التضحية سهولة الاستخدام.أنا استخدامها نفسي باستمرار العمل مع كمية كبيرة من الرسوم البيانية.

Answer 3

كما سبق ذكره ، NetworkX هو جيد جدا, مع خيار آخر يجري igraph.كل من وحدات سوف يكون معظم (إن لم يكن كل) أدوات تحليل أنت من المحتمل أن تحتاج كل المكتبات تستخدم بشكل روتيني مع الشبكات الكبيرة.

Answer 4

القاموس قد تحتوي أيضا على النفقات العامة حسب التنفيذ الفعلي.Hashtable عادة ما تحتوي على بعض الوزراء عدد من العقد المتاحة لتبدأ, حتى ولو كنت قد فقط استخدام زوجين من العقد.

اذا حكمنا من خلال المثال الخاص بك ، "الملكية" ، هل سيكون أفضل مع فئة نهج المستوى النهائي و الحقيقي الخصائص ؟ أو أسماء من خصائص تغيير الكثير من عقدة إلى عقدة?

أود أن أقول أن ما "كفاءة" يعني يعتمد على الكثير من الأشياء مثل:

• سرعة التحديثات (insert, update, delete)
• سرعة الوصول العشوائي استرجاع
• سرعة استرجاع متتابعة
• الذاكرة المستخدمة

أعتقد أنك سوف تجد أن بنية البيانات التي يتم الإسراع عموما سوف تستهلك ذاكرة أكثر من واحد الذي هو بطيء.هذا ليس هو الحال دائما, ولكن معظم هياكل البيانات يبدو أن يتبع هذا.

القاموس قد تكون سهلة الاستخدام و يعطيك موحد نسبيا الوصول السريع, فإنه من المرجح أن استخدام المزيد من الذاكرة ، كما تقترح القوائم.قوائم, لكن, عموما تميل إلى أن تحتوي على المزيد من النفقات العامة عند إدراج بيانات في ذلك ، إلا أنها preallocate X العقد ، والتي سوف تستخدم مرة أخرى المزيد من الذاكرة.

اقتراحي ، بصفة عامة ، أن مجرد استخدام الطريقة التي تبدو طبيعية لك ، ومن ثم القيام "اختبار الإجهاد" من النظام ، إضافة كمية كبيرة من البيانات إليها ومعرفة ما إذا كان يصبح مشكلة.

كنت قد تنظر أيضا في إضافة طبقة من التجريد إلى النظام الخاص بك, حتى لا تضطر إلى تغيير واجهة برمجة إذا كنت في وقت لاحق على ضرورة تغيير بنية البيانات الداخلية.

Answer 5

كما فهمت وصول عشوائي في وقت ثابت لكل بايثون dicts و قوائم الفرق هو أنه يمكنك فقط الوصول العشوائي من عدد الفهارس مع القوائم.أنا على افتراض أن كنت بحاجة إلى بحث عقدة قبل التسمية ، إذا كنت ترغب في ديكت من dicts.

ومع ذلك ، على أداء الجبهة ، تحميله في الذاكرة قد لا يكون مشكلة ، ولكن إذا كنت تستخدم أكثر من اللازم فسوف ينتهي مبادلة القرص الذي سوف يقتل أداء حتى بايثون كفاءة عالية dicts.في محاولة للحفاظ على الذاكرة أسفل قدر الإمكان.أيضا, RAM هي رخيصة بشكل مثير للدهشة الآن ؛ إذا كنت تفعل هذا النوع من الشيء الكثير, ليس هناك سبب لكي لا يكون على الأقل 4GB.

إذا كنت تريد المشورة بشأن حفظ واستخدام الذاكرة ، أعطي بعض المعلومات عن هذا النوع من المعلومات التي كنت تتبع كل عقدة.

Answer 6

مما يجعل فئة على أساس هيكل ربما يكون لديك المزيد من النفقات العامة من dict-بناء الهيكل ، بما في بيثون دروس في الواقع استخدام dicts عند تنفيذها.

Answer 7

لا شك NetworkX هو أفضل بنية البيانات حتى الآن على الرسم البياني.لأنه يأتي مع المرافق مثل وظائف المساعد, هياكل البيانات والخوارزميات ، تسلسل عشوائي مولدات, ديكور, Cuthill-ماكي ترتيب سياق مديري

NetworkX عظيم لأنه wowrs على الرسوم البيانية ، digraphs ، multigraphs.فإنه يمكن الكتابة مع الرسم البياني طرق متعددة:قائمة الجوار ، متعدد الجوار القائمة ، حافة القائمة ، GEXF ، GML.يعمل مع المخلل ، GraphML, سلمان, SparseGraph6.... الخ

وقد implimentation من مختلف radimade خوارزميات بما في ذلك:التقريب ، مشطور, الحدود, مركزية, زمرة, تجميع, تلوين, مكونات, الاتصال, دورات, توجه احلقي الرسوم البيانية ، المسافة التدابير ، التي تسيطر مجموعات ، Eulerian, التماثل, رابط التحليل, الرابط التنبؤ, مطابقة, الحد الأدنى شجرة الامتداد الغنية نادي أقصر الطرق ، اجتياز شجرة.