पायथन में सबसे कुशल ग्राफ डेटा संरचना क्या है?

Question

मुझे पायथन में एक बड़े (10^7 नोड्स) ग्राफ में हेरफेर करने में सक्षम होना चाहिए। प्रत्येक नोड/किनारे से संबंधित डेटा न्यूनतम है, कहें, स्ट्रिंग की एक छोटी संख्या। मेमोरी और गति के मामले में, यह करने का तरीका सबसे कुशल क्या है?

डिक्ट्स का एक नियम लागू करने के लिए अधिक लचीला और आसान है, लेकिन मैं सहजता से सूचियों की सूची को तेज़ी से उम्मीद करता हूं। सूची विकल्प भी आवश्यकता होगी कि मैं डेटा संरचना से अलग रखना है, जबकि dicts तरह कुछ के लिए अनुमति होगी:

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

आप क्या सुझाव है?

---

हां, मुझे दक्षता से मेरा क्या मतलब है पर थोड़ा स्पष्ट होना चाहिए था। इस विशेष मामले में मेरा मतलब यादृच्छिक पहुंच पुनर्प्राप्ति के संदर्भ में है।

स्मृति में डेटा लोड करना एक बड़ी समस्या नहीं है। यह एक बार और सभी के लिए किया जाता है। समय लेने वाला हिस्सा नोड्स पर जा रहा है, इसलिए मैं जानकारी निकाल सकता हूं और जिस मीट्रिक में दिलचस्पी रखता हूं उसे माप सकता हूं।

मैंने प्रत्येक नोड को कक्षा बनाने के लिए विचार नहीं किया था (गुण सभी नोड्स के लिए समान हैं) लेकिन ऐसा लगता है जैसे कि ओवरहेड की एक अतिरिक्त परत जोड़ना होगा? मैं उम्मीद कर रहा था कि किसी को भी इसी तरह के मामले के साथ कुछ सीधा अनुभव होगा कि वे साझा कर सकते हैं। आखिरकार, सीएस में ग्राफ सबसे आम अमूर्तताओं में से एक हैं।

Answer 1

मैं आपको दृढ़ता से सलाह देता हूं कि आप NetworkX देखें। यह एक युद्ध-परीक्षण युद्ध घोड़ा है और पहला उपकरण अधिकांश 'शोध' प्रकार तब तक पहुंचता है जब उन्हें नेटवर्क आधारित डेटा का विश्लेषण करने की आवश्यकता होती है। मैंने नोटबुक पर समस्या के बिना 100 हजारों किनारों के साथ ग्राफों का उपयोग किया है। इसकी सुविधा समृद्ध और उपयोग करने में बहुत आसान है। अंतर्निहित कार्यान्वयन में ब्योरे के बजाय आप स्वयं को समस्या पर अधिक ध्यान केंद्रित करेंगे।

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

वास्तविक कार्यान्वयन के आधार पर एक शब्दकोश में ओवरहेड भी हो सकता है। एक हैशटेबल में आमतौर पर उपलब्ध नोड्स की कुछ प्रमुख संख्या होती है, भले ही आप केवल कुछ नोड्स का उपयोग कर सकें।

आपके उदाहरण, "संपत्ति" के आधार पर, क्या आप अंतिम स्तर और वास्तविक गुणों के लिए कक्षा दृष्टिकोण के साथ बेहतर होंगे? या गुणों के नाम नोड से नोड में बहुत बदल रहे हैं?

मैं कहना चाहता हूँ कि क्या "कुशल" का अर्थ है, बहुत कुछ इस पर निर्भर करता है जैसे:

• अद्यतन (डालने, अद्यतन करना, हटाना)
• रैंडम एक्सेस पुनः प्राप्ति की गति की गति
• अनुक्रमिक पुनर्प्राप्ति
• स्मृति का उपयोग किया

मुझे लगता है कि आप मिल जाएगा की गति है कि एक डेटा संरचना है कि आम तौर पर होगा ग तेजी से है धीमी गति से अधिक स्मृति को ऑन्यूम करें। यह हमेशा मामला नहीं है, लेकिन अधिकांश डेटा संरचनाएं इसका पालन करती हैं।

एक शब्दकोश का उपयोग करना आसान हो सकता है, और आपको अपेक्षाकृत समान रूप से तेज़ पहुंच प्रदान करता है, जैसा कि आप सुझाते हैं, सूचियों की तुलना में अधिक स्मृति का उपयोग करेंगे। हालांकि, जब आप डेटा को सम्मिलित करते हैं, तब तक आमतौर पर अधिक ओवरहेड होते हैं, जब तक वे एक्स नोड्स को प्रीलोकेट नहीं करते हैं, जिसमें वे फिर से अधिक मेमोरी का उपयोग करेंगे।

मेरा सुझाव, सामान्य रूप से, उस पद्धति का उपयोग करना होगा जो आपके लिए सबसे स्वाभाविक प्रतीत होता है, और फिर सिस्टम का "तनाव परीक्षण" करता है, इसमें पर्याप्त मात्रा में डेटा जोड़ता है और देखता है कि यह हो जाता है या नहीं एक समस्या।

आप अपने सिस्टम में अमूर्तता की एक परत जोड़ने पर भी विचार कर सकते हैं, ताकि आपको बाद में आंतरिक डेटा संरचना को बदलने की आवश्यकता होने पर प्रोग्रामिंग इंटरफ़ेस को बदलने की आवश्यकता न हो।

Answer 3

कक्षा-आधारित संरचना बनाना संभवतया ताना-आधारित संरचना की तुलना में अधिक ओवरहेड होगा, क्योंकि पाइथन कक्षाएं वास्तव में लागू होने पर डिक्ट्स का उपयोग करती हैं।

Answer 4

जैसा कि मैं इसे समझता हूं, यादृच्छिक पहुंच दोनों पायथन के डिक्ट्स और सूचियों के लिए निरंतर समय में है, अंतर यह है कि आप केवल सूचियों के साथ पूर्णांक अनुक्रमणिका का यादृच्छिक उपयोग कर सकते हैं। मुझे लगता है कि आपको अपने लेबल द्वारा नोड को देखने की ज़रूरत है, इसलिए आप डिक्ट्स का एक नियम चाहते हैं।

हालांकि, प्रदर्शन मोर्चे पर, इसे स्मृति में लोड करना कोई समस्या नहीं हो सकती है, लेकिन यदि आप बहुत अधिक उपयोग करते हैं तो आप डिस्क पर स्वैपिंग समाप्त कर देंगे, जो कि पाइथन की अत्यधिक कुशल डाइट्स के प्रदर्शन को भी मार देगा। जितना संभव हो सके स्मृति उपयोग को कम रखने की कोशिश करें। इसके अलावा, राम अभी आश्चर्यजनक रूप से सस्ते है; यदि आप इस तरह की चीज बहुत करते हैं, तो कम से कम 4 जीबी नहीं होने का कोई कारण नहीं है।

यदि आप स्मृति उपयोग को कम रखने के बारे में सलाह चाहते हैं, तो प्रत्येक नोड के लिए आप जिस प्रकार की जानकारी ट्रैक कर रहे हैं, उसके बारे में कुछ और जानकारी दें।

Answer 5

जैसा कि पहले ही उल्लेख किया है, NetworkX बहुत है चले जाओ ओडी, एक और विकल्प igraph के साथ। दोनों मॉड्यूल में सबसे अधिक (यदि नहीं सभी) विश्लेषण उपकरण होंगे जिनकी आपको आवश्यकता हो सकती है, और दोनों पुस्तकालय नियमित रूप से बड़े नेटवर्क के साथ उपयोग किए जाते हैं।

Answer 6

हालांकि यह प्रश्न अब काफी पुराना है, मुझे लगता है कि ग्राफ मैनिपुलेशन के लिए graph-tool नामक मेरे अपने पायथन मॉड्यूल का उल्लेख करना उचित है। यह बहुत ही कुशल है, चूंकि बूस्ट ग्राफ लाइब्रेरी का उपयोग करते हुए टेम्पलेट मेटाप्रोग्रामिंग के साथ सी ++ में डेटा संरचनाओं और एल्गोरिदम लागू किए जाते हैं। इसलिए इसका प्रदर्शन (स्मृति उपयोग और रनटाइम दोनों में) शुद्ध सी ++ लाइब्रेरी से तुलनीय है, और उपयोग की आसानी को बलि किए बिना, सामान्य पायथन कोड से बेहतर परिमाण के आदेश हो सकता है। मैं इसे अपने आप को बहुत बड़े ग्राफ के साथ काम करने के लिए लगातार उपयोग करता हूं।

Answer 7

इसमें कोई संदेह नहीं है कि अब तक नेटवर्क के लिए नेटवर्कएक्स सबसे अच्छी डेटा संरचना है। यह हेल्पर फ़ंक्शन, डेटा स्ट्रक्चर और एल्गोरिदम, रैंडम अनुक्रम जेनरेटर, सजावटी, कुथिल-मैकी ऑर्डरिंग, कंटेक्स्ट मैनेजर

नेटवर्कएक्स बहुत अच्छा है क्योंकि यह ग्राफ, डिग्राफ और मल्टीग्राफ के लिए वाहक है। यह कई तरीकों से ग्राफ लिख सकता है: एडजेंसी सूची, मल्टीलाइन एडजेंसी सूची, एज सूची, जीएक्सएफ, जीएमएल। यह पिकल, ग्राफएमएल, जेएसओएन, स्पैर्सग्राफ 6 आदि के साथ काम करता है।

यह सहित विभिन्न radimade एल्गोरिदम के implimentation है: सन्निकटन, द्विपक्षीय, सीमा, केन्द्रीयता, गुट, क्लस्टरिंग, रंग, घटक, कनेक्टिविटी, साइकिल, निर्देशित अचक्रीय रेखांकन, दूरी के उपाय, हावी सेट, Eulerian, समाकृतिकता, लिंक विश्लेषण, लिंक भविष्यवाणी, मिलान, न्यूनतम स्पैनिंग ट्री, रिच क्लब, सबसे छोटा पथ, ट्रैवर्सल, ट्री।