real - ¿Cuál es la estructura de datos gráficos más eficiente en Python?

python graficos 2d

Question

Necesito poder manipular un gráfico grande (10 ^ 7 nodos) en python. Los datos correspondientes a cada nodo / borde son mínimos, digamos, un pequeño número de cadenas. ¿Cuál es la forma más eficiente, en términos de memoria y velocidad , de hacer esto?

Un dictado de dictados es más flexible y más sencillo de implementar, pero intuitivamente espero que una lista de listas sea más rápida. La opción de lista también requeriría que mantenga los datos separados de la estructura, mientras que los dictados permitirían algo por el estilo:

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

¿Qué sugieres?

Sí, debería haber sido un poco más claro sobre lo que quiero decir con eficiencia. En este caso particular, lo digo en términos de recuperación de acceso aleatorio.

Cargar los datos en la memoria no es un gran problema. Eso se hace de una vez por todas. La parte que consume más tiempo es visitar los nodos para poder extraer la información y medir las métricas que me interesan.

No había considerado hacer de cada nodo una clase (las propiedades son las mismas para todos los nodos) pero parece que eso agregaría una capa adicional de sobrecarga. Esperaba que alguien tuviera alguna experiencia directa con un caso similar que pudieran compartir. Después de todo, los gráficos son una de las abstracciones más comunes en CS.

Answer 1

Aunque esta pregunta ahora es bastante antigua, creo que vale la pena mencionar mi propio módulo de Python para la manipulación de gráficos llamado herramienta de gráficos . Es muy eficiente, ya que las estructuras de datos y los algoritmos se implementan en C ++, con metaprogramación de plantillas, utilizando la Biblioteca de gráficos Boost. Por lo tanto, su rendimiento (tanto en el uso de la memoria como en el tiempo de ejecución) es comparable a una biblioteca C ++ pura y puede ser mucho mejor que el código típico de Python, sin sacrificar la facilidad de uso. Lo uso constantemente para trabajar con gráficos muy grandes.

Answer 2

Como ya se mencionó, NetworkX es muy bueno, con otra opción que es igraph . Ambos módulos tendrán la mayoría (si no todas) las herramientas de análisis que probablemente necesitará, y ambas bibliotecas se usan de manera rutinaria con redes grandes.

Answer 3

Hacer una estructura basada en clases probablemente tendría más sobrecarga que la estructura basada en dict, ya que en Python las clases realmente usan dictos cuando se implementan.

Answer 4

Recomiendo encarecidamente que mire NetworkX . Es un caballo de guerra probado en batalla y la primera herramienta que la mayoría de los tipos de ''investigación'' alcanzan cuando necesitan hacer un análisis de datos basados ​​en la red. He manipulado gráficos con cientos de miles de bordes sin problemas en una computadora portátil. Su característica rica y muy fácil de usar. Te encontrarás centrándote más en el problema en cuestión que en los detalles de la implementación subyacente.

Ejemplo de generación y análisis de gráficos aleatorios de 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 ([email protected])"""
__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)

Las visualizaciones también son sencillas:

Más visualización: http://jonschull.blogspot.com/2008/08/graph-visualization.html

Answer 5

Según tengo entendido, el acceso aleatorio está en tiempo constante tanto para los dictados como para las listas de Python, la diferencia es que solo puede hacer acceso aleatorio de índices enteros con listas. Supongo que necesita buscar un nodo por su etiqueta, por lo que desea un dictado de dictados.

Sin embargo, en el frente del rendimiento, cargarlo en la memoria puede no ser un problema, pero si usa demasiado, terminará cambiando al disco, lo que matará el rendimiento incluso de los dictados altamente eficientes de Python. Intente mantener el uso de memoria bajo tanto como sea posible. Además, la RAM es increíblemente barata en este momento; Si haces mucho este tipo de cosas, no hay razón para no tener al menos 4 GB.

Si desea consejos sobre cómo mantener bajo el uso de memoria, brinde más información sobre el tipo de información que está rastreando para cada nodo.

Answer 6

Sin duda, NetworkX es la mejor estructura de datos hasta ahora para gráficos. Viene con utilidades como funciones auxiliares, estructuras de datos y algoritmos, generadores de secuencia aleatoria, decoradores, pedidos de Cuthill-Mckee, gestores de contexto

NetworkX es excelente porque ofrece gráficos, dígrafos y multigrafos. Puede escribir gráficos con múltiples formas: Lista de adyacencia, Lista de adyacencia multilínea, Lista de bordes, GEXF, GML. Funciona con Pickle, GraphML, JSON, SparseGraph6, etc.

Implica varios algoritmos de radimade, que incluyen: aproximación, bipartito, límite, centralidad, camarilla, agrupación, coloración, componentes, conectividad, ciclos, gráficos acíclicos dirigidos, medidas de distancia, conjuntos de dominación, euleriano, isomorfismo, análisis de enlaces, predicción de enlaces, coincidencia , Árbol de expansión mínima, Club rico, Caminos más cortos, Recorrido, Árbol.

Answer 7

Un diccionario también puede contener gastos generales, dependiendo de la implementación real. Para empezar, una tabla hash generalmente contiene un número primo de nodos disponibles, aunque solo puede usar un par de nodos.

A juzgar por su ejemplo, "Propiedad", ¿sería mejor con un enfoque de clase para el nivel final y las propiedades reales? ¿O los nombres de las propiedades cambian mucho de un nodo a otro?

Yo diría que lo que significa "eficiente" depende de muchas cosas, como:

• velocidad de actualizaciones (insertar, actualizar, eliminar)
• velocidad de recuperación de acceso aleatorio
• velocidad de recuperación secuencial
• memoria usada

Creo que encontrará que una estructura de datos que es rápida generalmente consumirá más memoria que una que sea lenta. Este no es siempre el caso, pero la mayoría de las estructuras de datos parecen seguir esto.

Un diccionario puede ser fácil de usar y proporcionarle un acceso relativamente rápido y uniforme, lo más probable es que use más memoria que, como sugiere, las listas. Sin embargo, las listas generalmente tienden a contener más sobrecarga cuando inserta datos en ella, a menos que preasignen nodos X, en los que volverán a utilizar más memoria.

Mi sugerencia, en general, sería usar el método que le parezca más natural y luego hacer una "prueba de esfuerzo" del sistema, agregando una cantidad sustancial de datos y ver si se convierte en un problema.

También puede considerar agregar una capa de abstracción a su sistema, de modo que no tenga que cambiar la interfaz de programación si más tarde necesita cambiar la estructura de datos interna.