Ποια είναι η πιο αποτελεσματική δομή δεδομένων γράφου σε Python;

ψήφοι
63

Θα πρέπει να είναι σε θέση να χειριστούν ένα μεγάλο (10 ^ 7 κόμβων) γράφημα σε python. Τα δεδομένα που αντιστοιχούν σε κάθε κόμβο / ακμή είναι ελάχιστη, ας πούμε, ένας μικρός αριθμός των στοιχειοσειρών. Ποια είναι η πιο αποτελεσματική, από την άποψη της μνήμης και την ταχύτητα , τον τρόπο για να γίνει αυτό;

Μια dict της DICTS είναι πιο ευέλικτη και απλούστερη στην εφαρμογή, αλλά διαισθητικά περιμένουμε μια λίστα με τις λίστες να είναι ταχύτερη. Η επιλογή κατάλογος θα απαιτήσει, επίσης, ότι θα κρατήσει τα στοιχεία χωριστά από τη δομή, ενώ DICTS θα επέτρεπε κάτι τέτοιο:

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

Τι θα προτείνατε;


Ναι, θα έπρεπε να ήταν λίγο πιο σαφής για το τι εννοώ με την αποτελεσματικότητα. Στη συγκεκριμένη περίπτωση το εννοώ από την άποψη της τυχαίας ανάκτηση πρόσβασης.

Τοποθέτηση των δεδομένων στη μνήμη δεν είναι ένα τεράστιο πρόβλημα. Αυτό κάνει μια για πάντα. Το τμήμα χρονοβόρα επισκέπτεται τους κόμβους ώστε να μπορώ να συλλέξει τις πληροφορίες και να μετρήσουν τις μετρήσεις που με ενδιαφέρει.

Δεν είχε θεωρηθεί κάνει κάθε κόμβος μια κατηγορία (ιδιότητες είναι οι ίδιες για όλους τους κόμβους), αλλά φαίνεται ότι αυτό θα προσθέσει ένα επιπλέον στρώμα πάνω από το κεφάλι; Ήλπιζα κάποιος θα έχουν κάποια άμεση εμπειρία με παρόμοια υπόθεση που θα μπορούσαν να μοιραστούν. Μετά από όλα, τα γραφήματα είναι ένα από τα πιο κοινά αφαιρέσεις στο CS.

Δημοσιεύθηκε 04/08/2008 στις 13:00
πηγή χρήστη
Σε άλλες γλώσσες...                            


7 απαντήσεις

ψήφοι
51

Θα ήθελα να προτείνω ανεπιφύλακτα να δείτε 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

Απαντήθηκε 26/08/2008 στις 18:43
πηγή χρήστη

ψήφοι
12

Ακόμα κι αν αυτή η ερώτηση είναι τώρα αρκετά παλιά, νομίζω ότι αξίζει τον κόπο να αναφέρω τη δική ενότητα python μου για χειραγώγηση γράφημα ονομάζεται διάγραμμα-εργαλείο . Είναι πολύ αποτελεσματικό, δεδομένου ότι οι δομές δεδομένων και αλγόριθμοι εφαρμόζονται σε C ++, με πρότυπο metaprograming, χρησιμοποιώντας το Boost Graph Library. Ως εκ τούτου επιδόσεων του (και τα δύο σε χρήση μνήμης και χρόνου εκτέλεσης) είναι συγκρίσιμη με μια καθαρή βιβλιοθήκη C ++, και μπορεί να είναι τάξεις μεγέθους καλύτερη από τυπικό κώδικα Python, χωρίς να θυσιάζεται η ευκολία χρήσης. Το χρησιμοποιώ τον εαυτό μου συνεχώς να συνεργαστεί με πολύ μεγάλα διαγράμματα.

Απαντήθηκε 27/11/2010 στις 15:10
πηγή χρήστη

ψήφοι
6

Όπως έχει ήδη αναφερθεί, NetworkX είναι πολύ καλό, με μια άλλη επιλογή είναι igraph . Και οι δύο μονάδες θα έχουν περισσότερες (αν όχι όλες) τα εργαλεία ανάλυσης που είναι πιθανό να χρειάζονται και οι δύο βιβλιοθήκες που χρησιμοποιούνται συνήθως με τα μεγάλα δίκτυα.

Απαντήθηκε 27/08/2008 στις 11:01
πηγή χρήστη

ψήφοι
4

Ένα λεξικό μπορεί επίσης να περιέχει γενικά, ανάλογα με την πραγματική εφαρμογή. Μια hashtable συνήθως περιέχουν κάποια πρώτος αριθμός των διαθέσιμων κόμβων για να αρχίσει με, αν και μπορείτε να χρησιμοποιήσετε μόνο ένα ζευγάρι των κόμβων.

Κρίνοντας από το παράδειγμά σας, «Ακίνητα», θα ήταν καλύτερα της με μια προσέγγιση κατηγορίας για το τελικό επίπεδο και πραγματικές ιδιότητες; Ή είναι τα ονόματα των ιδιοτήτων αλλάζει πολλά από κόμβο σε κόμβο;

Θα έλεγα ότι αυτό που «αποτελεσματικό» μέσο εξαρτάται από πολλά πράγματα, όπως:

  • Ταχύτητα του προϊόντος (εισαγωγή, ενημέρωση, διαγραφή)
  • ταχύτητα τυχαίας ανάκτηση της πρόσβασης
  • ταχύτητα της διαδοχικής ανάκτησης
  • μνήμης που χρησιμοποιείται

Νομίζω ότι θα βρείτε ότι μια δομή δεδομένων που είναι ταχεία γενικά καταναλώνουν περισσότερη μνήμη από αυτή που είναι αργή. Αυτό δεν συμβαίνει πάντα, αλλά τις δομές περισσότερα στοιχεία φαίνεται να ακολουθεί αυτή.

Ένα λεξικό μπορεί να είναι εύκολο στη χρήση, και θα σας δώσει σχετικά ομοιόμορφα γρήγορη πρόσβαση, θα χρησιμοποιήσει πιθανότατα περισσότερη μνήμη από ό, τι, όπως προτείνουν, λίστες. Λίστες, όμως, γενικά τείνουν να περιέχουν περισσότερο γενικά όταν εισάγετε δεδομένα σε αυτό, εκτός αν preallocate Χ κόμβους, με την οποία θα χρησιμοποιήσει και πάλι περισσότερη μνήμη.

Η πρότασή μου, σε γενικές γραμμές, είναι να χρησιμοποιήσετε απλά τη μέθοδο που φαίνεται το πιο φυσικό για εσάς, και στη συνέχεια να κάνουν ένα «τεστ αντοχής» του συστήματος, προσθέτοντας ένα σημαντικό ποσό των δεδομένων σε αυτό και να δούμε αν αυτό γίνεται ένα πρόβλημα.

Μπορείτε επίσης να προσθέσετε ένα στρώμα αφαίρεσης στο σύστημά σας, έτσι ώστε να μην χρειάζεται να αλλάξετε τη διεπαφή προγραμματισμού, εάν αργότερα ανάγκη να αλλάξει η εσωτερική δομή των δεδομένων.

Απαντήθηκε 04/08/2008 στις 13:09
πηγή χρήστη

ψήφοι
3

Όπως το αντιλαμβάνομαι, τυχαίας προσπέλασης είναι σε συνεχή χρόνο τόσο για DICTS και τις λίστες της Python, η διαφορά είναι ότι μπορείτε να το κάνετε μόνο τυχαίας προσπέλασης των δεικτών ακέραιο με λίστες. Υποθέτω ότι θα πρέπει να αναζήτηση ενός κόμβου από την ετικέτα του, έτσι θέλετε ένα dict της DICTS.

Ωστόσο, στο μέτωπο απόδοση, φορτώνοντάς το στη μνήμη δεν μπορεί να είναι ένα πρόβλημα, αλλά αν χρησιμοποιείτε πάρα πολύ θα καταλήξετε εναλλαγή στο δίσκο, η οποία θα σκοτώσει την απόδοση του ακόμα και υψηλής απόδοσης DICTS της Python. Προσπαθήστε να κρατήσετε τη χρήση μνήμης προς τα κάτω όσο το δυνατόν περισσότερο. Επίσης, μνήμη RAM είναι εκπληκτικά φθηνή αυτή τη στιγμή? Αν το κάνετε αυτό το είδος του πράγματος πολλά, δεν υπάρχει κανένας λόγος να μην έχει τουλάχιστον 4GB.

Αν θέλετε συμβουλές σχετικά με τη διατήρηση χρήση μνήμης προς τα κάτω, να δώσει κάποιες περισσότερες πληροφορίες σχετικά με το είδος των πληροφοριών που παρακολουθείτε για κάθε κόμβο.

Απαντήθηκε 06/08/2008 στις 06:37
πηγή χρήστη

ψήφοι
2

Κάνοντας μια ταξική δομή που βασίζεται θα έχουν κατά πάσα πιθανότητα πιο γενικά από τη δομή dict-based, αφού στις τάξεις python χρησιμοποιούν πραγματικά DICTS κατά την εφαρμογή τους.

Απαντήθηκε 04/08/2008 στις 13:41
πηγή χρήστη

ψήφοι
1

Δεν υπάρχει αμφιβολία ότι NetworkX είναι η καλύτερη δομή δεδομένων μέχρι τώρα για το διάγραμμα. Έρχεται με επιχειρήσεις κοινής ωφέλειας, όπως Λειτουργίες Helper, Δομές Δεδομένων και Αλγόριθμοι, γεννήτριες τυχαίων Ακολουθία, Διακοσμητές, Cuthill-Mckee παραγγελίας, Διευθυντές Πλαίσιο

NetworkX είναι μεγάλη, διότι wowrs για γραφήματα, διγράμματα και multigraphs. Μπορεί να γράψει γράφημα με πολλούς τρόπους: γειτνίασης Λίστα, Multiline γειτνίασης Λίστα, Edge Λίστα, GEXF, GML. Λειτουργεί με τουρσιών, GraphML, JSON, SparseGraph6 κ.λπ.

Έχει εφαρμογής καθώς των διαφόρων radimade αλγορίθμων μεταξύ των οποίων: Προσέγγιση, διμερής, Όριο, κεντρική τοποθεσία, Clique, Ομαδοποίηση, χρωματισμός, Εξαρτήματα, Συνδεσιμότητα, Κύκλοι, κατευθυνόμενος άκυκλος γράφος, Απόσταση μέτρα, Κυριαρχούν Σκηνικά, Eulerian, ισομορφισμός, Ανάλυση Link, Πρόβλεψη Link, Αντιστοίχιση , ελάχιστο spanning tree, Rich Club, Συντομότερη Μονοπάτια, διέλευσης, δέντρο.

Απαντήθηκε 18/01/2016 στις 09:08
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more