Grafik-Tool überraschend langsam im Vergleich zu Networkx

Question

Nach dem Blick auf die beeindruckende performance comparison, entschied ich, dass ich versuchen würde, Graph-Tool. Zum Vergleich habe ich Codes geschrieben, um einen zufälligen Baum mit beiden Paketen zu erzeugen.

Der Grafik-Werkzeug-Code:

import numpy as np 
import graph_tool.all as gt 

# construct an initial graph with two nodes and one link 
n = 5000 
G = gt.Graph(directed = False) 
G.add_edge(0, 1) 

for t in range(2, n): 
    # connect the new vertex to one of the old vertices randomly 
    G.add_edge(np.random.choice(range(t)), t) 

Der Code NetworkX:

import networkx as nx 
import numpy as np 

n = 5000 
# initial graph 
G = nx.Graph() 
G.add_edge(0, 1) 

for t in range(2, n): 
    G.add_edge(t, np.random.choice(range(t))) 

Das Grafik-Werkzeug, dauert etwa 14 Sekunden auf meiner 4-Core-Maschine während NetworkX dauert weniger als 2 Sekunden auf die gleiche Maschine! Fehle ich etwas Offensichtliches?

Vielen Dank im Voraus.

Answer 1

Hier ist nichts überraschend. graph-tool erreicht eine höhere Leistung, indem Hauptschleifen in C++ ausgelagert werden. Wenn alle Haupt-Schleifen in Python sind, bietet das keinen Vorteil. Das gleiche gilt für andere Bibliotheken wie numpy.

Der richtige Weg, um eine schnelle Addition von Kanten zu erreichen, ist, dass das Graph-Tool die Hauptschleife ausführt. Das Netzwerk Sie generieren ist ein einfaches Wachstumsmodell, und kann durch den Aufruf im Graph-Werkzeug erreicht werden:

G = price_network(n, gamma=0, directed=False) 

, die Fahrt dauert ca. 15 ms in meinem Computer für n = 5000.

Beachten Sie auch, dass Ihr Python-Code unnötig langsam ist, da Sie bei jeder Iteration neue Listen mit allen Stützpunkten erstellen. Eine viel schnellere Version wäre:

from numpy.random import randint 
n = 5000 
G = Graph(directed=False) 
G.add_vertex(n) 
G.add_edge(0, 1) 
for i in range(2, n): 
    G.add_edge(i, randint(i)) 

Für eine noch größere Werte von n, wird es noch schneller sein, alle Kanten auf einmal hinzuzufügen, statt einer nach dem anderen, das heißt

from graph_tool.all import * 
from numpy.random import randint 
n = 5000 
G = Graph(directed=False) 
edges = [(0, 1)] 
for i in range(2, n): 
    edges.append((i, randint(i))) 
G.add_edge_list(edges)