Jaký je nejúčinnější konstrukce graf dat v Pythonu?

hlasů
63

Musím být schopni manipulovat s velkou (10 ^ 7) uzly grafu v pythonu. Data odpovídající každému uzlu / EDGE je minimální, řekněme, malý počet řetězců. Jaký je nejúčinnější, pokud jde o paměti a rychlosti , způsob, jak dělat to?

Dict of dicts je pružnější a jednodušší implementovat, ale intuitivně očekávají seznam seznamů být rychlejší. Volba seznamu by také požadovat, aby pořád data oddělit od struktury, zatímco dicts by umožnila něco takového:

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

Co byste navrhovali?


Ano, měl jsem být trochu jasnější, co tím myslím účinnosti. V tomto konkrétním případě mám na mysli to, pokud jde o náhodné získávání přístupu.

Načítání dat do paměti není velký problém. Že to udělal jednou provždy. Časově náročná část je na návštěvě uzly, takže mohu extrahovat informace a měřit metriky mě zajímá.

Neměl jsem zvažoval, že dělá každý uzel třída (vlastnosti jsou stejné pro všechny uzly), ale vypadá to, že by se přidat další vrstvu nad hlavou? Doufal jsem, že někdo bude mít nějakou přímou zkušenost s podobný případ, že by mohli sdílet. Koneckonců, grafy jsou jedním z nejčastějších abstrakcí v CS.

Položena 04/08/2008 v 13:00
zdroj uživatelem
V jiných jazycích...                            


7 odpovědí

hlasů
51

Chtěl bych důrazně prosazovat se podíváte na NetworkX . Je to bitva testovány válečné koně a první nástroj většina ‚Výzkum‘ typy dosáhnout, když je třeba udělat analýzu sítě na bázi dat. Jsem manipulovat grafy s 100s tisíc hran bez problémů na notebooku. Jeho funkce bohatý a velmi snadno se používá. Ocitnete se zaměřuje více na problém po ruce, spíše než podrobnosti v podkladové implementaci.

Příklad Erdős-Rényiho generování náhodných a analýzu grafů


"""
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)

Vizualizace jsou také jednoduché:

zadejte popis obrázku zde

Další vizualizace: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Odpovězeno 26/08/2008 v 18:43
zdroj uživatelem

hlasů
12

I přesto, že tato otázka je teď docela starý, myslím, že to stojí za to zmínit svou vlastní python modul pro graf manipulaci s názvem graf-tool . To je velmi efektivní, protože datové struktury a algoritmy jsou implementovány v jazyce C ++, s šablony metaprograming pomocí Boost Graph Library. Proto je jeho výkon (a to jak v paměti nebo délky běhu) je srovnatelná s čistě C knihovny ++, a mohou být o několik řádů vyšší, než je obvyklé python kódu, aniž by byla obětována snadnost použití. Používám ji sám neustále pracovat s velkými grafy.

Odpovězeno 27/11/2010 v 15:10
zdroj uživatelem

hlasů
6

Jak již bylo zmíněno, NetworkX je velmi dobrá, s jinou možnost bytí igraph . Oba moduly budou mít většinu (ne-li všechny), nástroje analýzy, které vás pravděpodobně potřebovat, a obě knihovny se běžně používají u velkých sítí.

Odpovězeno 27/08/2008 v 11:01
zdroj uživatelem

hlasů
4

Slovník může obsahovat i nad hlavou, v závislosti na skutečné realizaci. HashTable obvykle obsahují určité prvočíslo dostupných uzlů Za prvé, i když byste mohli používat jen pár uzlů.

Soudě podle vašeho příkladu, „vlastnictví“, měli byste být lepší s třídního přístupu pro konečné úrovně a nemovitostí? Nebo názvy vlastností měnící se hodně od uzlu k uzlu?

Řekl bych, že to, co „účinný“ znamená, závisí na mnoha věcech, jako jsou:

  • Rychlost aktualizace (insert, aktualizovat, mazat)
  • Rychlost náhodného vyhledávání přístupového
  • Rychlost sekvenčního vyhledávání
  • paměť používaná

Myslím, že zjistíte, že datová struktura, která je rychlá obecně spotřebují více paměti než ten, který je pomalý. To není vždy případ, ale většina datových struktur se zdá následovat to.

Slovník může být snadno ovladatelný, a dá vám relativně rovnoměrně rychlý přístup, bude to s největší pravděpodobností používat více paměti než, jak si navrhnout, seznamy. Seznamy, ale obecně mají tendenci obsahovat další režii při vkládání dat do něj, pokud se předem přidělit X uzly, ve kterém se opět využívají více paměti.

Můj návrh, obecně by se stačí použít metodu, která se zdá být nejpřirozenější pro vás, a pak provést „zátěžový test“ systému, přidání značné množství dat na něj a uvidíme, jestli to bude problém.

Můžete také zvážit přidání vrstvu abstrakce do svého systému, takže nemusíte měnit programovací rozhraní Pokud se později o potřebě změnit vnitřní strukturu dat.

Odpovězeno 04/08/2008 v 13:09
zdroj uživatelem

hlasů
3

Jak jsem pochopil, náhodný přístup je v konstantním čase pro oba dicts a seznamů Python, rozdíl je, že můžete udělat jen náhodný přístup celočíselných indexů se seznamy. Jsem za předpokladu, že budete potřebovat k vyhledávání uzel svou značkou, takže chcete dict z dicts.

Nicméně, na přední straně výkonu, načtením do paměti nemusí být problém, ale pokud budete používat příliš mnoho skončíš swapování na disk, který zabije výkon i vysoce účinných dicts Python. Snažte se udržet využití paměti dolů, stejně jako je to možné. Také, RAM je teď úžasně levné; pokud si takové věci hodně, není to žádný důvod, proč mít alespoň 4 GB.

Pokud byste se chtěli poradit o udržení využití paměti dolů, dát nějaké další informace o druhu informací, které sledujete na každém uzlu.

Odpovězeno 06/08/2008 v 06:37
zdroj uživatelem

hlasů
2

Tvorba struktury třídní bázi by pravděpodobně mít větší režii než struktury dict bázi, protože v python tříd skutečně používat dicts při jejich provádění.

Odpovězeno 04/08/2008 v 13:41
zdroj uživatelem

hlasů
1

Není pochyb o tom NetworkX je nejlepší datová struktura dodnes pro graf. Dodává se s utilit jako pomocné funkce, datové struktury a algoritmy, náhodném pořadí generátory, dekoratéry Cuthill-McKee objednání, kontext manažery

NetworkX je skvělé, protože to wowrs pro grafy, digraphs a multigraf. Je možné psát graf s několika způsoby: Blízkost seznamu Multiline Blízkost, SEZNAM Edge GEXF, GML. Pracuje s okurky, GraphML, JSON, SparseGraph6 atd.

Má implimentation různých radimade algoritmů, včetně: Přibližování dvoustranný, ohraničující, Centrality, Clique, Clustering, barvení, komponenty, konektivita, cykly, Síťové grafy, vzdálenost opatření, dominující Sady, Eulerian, izomorfismus, Link Analysis, Link Prediction, Matching Minimum Spanning Tree, Rich Club, nejkratší cesty, Traversal, Tree.

Odpovězeno 18/01/2016 v 09:08
zdroj uživatelem

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