Schnellste Methode zum Durchlaufen von Indexpaaren in Python mithilfe von Numpy ⇐ Python

[Guest]

Ich erstelle einen Graphen mit ca. 10.000 Knoten, wobei jeder Knoten über Metadaten verfügt, die bestimmen, mit welchen anderen Knoten er mithilfe einer Kante verbunden wird.

Da die Anzahl der Kantenmöglichkeiten (~50 Mio ) weitaus größer ist als die tatsächliche Anzahl der Kanten, die hinzugefügt werden (~300.000), ist es nicht optimal, nur Knotenpaare mit for-Schleifen zu durchlaufen, um zu prüfen, ob eine Kante zwischen ihnen hinzugefügt werden sollte. Mit etwas Logik, um viele Paare herauszufiltern, damit sie nicht überprüft werden müssen, habe ich mit Hilfe der schnellen Methoden von numpy die Möglichkeiten schnell auf ein Array von nur ~30 Millionen Paaren reduziert.

Allerdings , wenn man stattdessen durch sie iteriert, hat sich die Leistung nicht wesentlich verbessert – tatsächlich ist das Iterieren durch eine größere 2D-Boolesche Matrix doppelt so schnell (im Vergleich zu meiner Methode, die zuvor die True-Werte aus der Matrix gesammelt und nur durchlaufen hat diese ~30 Millionen Instanzen). Es muss einen Weg geben, den gewünschten Leistungsvorteil zu erzielen, aber ich bin in eine Sackgasse geraten, weil ich herausfinden wollte, warum manche Methoden schneller sind und wie ich meine Laufzeit verbessern kann.

Kontext: Insbesondere ist jeder Knoten ein Künstler mit Metadaten wie Standorten, Geburts- und Sterbejahr.

Ich verbinde zwei Künstler auf der Grundlage einer Methode, die ein Maß dafür berechnet, wie nah sie sind ungefähr zur gleichen Zeit zusammenlebten (z. B. zwei Künstler, die gleichzeitig lebten). Ort zur gleichen Zeit und über einen ausreichend langen Zeitraum würde einen hohen Wert erhalten). Dies ist eine typische Methode, um genau das zu erreichen (die Iteration durch Indizes wird gegenüber Namen bevorzugt):

Code: Select all

for i, j in itertools.combinations(range(len(artist_names)), 2): #~50M iterations
artist1 = artist_names[i]
artist2 = artist_names[j]
#...
artist1_data = artist_data[artist1]
artist2_data = artist_data[artist2]

val = process.get_loc_similarity(artist1_data, artist2_data)

if val > 0:
G.add_edge(artist1, artist2, weight=val)

Da die Anzahl der Knotenpaare etwa 50 Millionen beträgt, dauert dies ~14 Minuten. Ich habe die Anzahl der Möglichkeiten reduziert, indem ich Künstlerpaare heraussortiert habe, deren Lebensläufe sich nicht überschnitten. Da die Methoden von numpy C unter der Haube ausführen, wurde dies in weniger als 5 Sekunden ausgeführt und es wurden ca. 30 Millionen Paare gesammelt, die nur überprüft werden mussten:

Code: Select all

birth_condition_matrix = (birth_years < death_years.reshape(-1, 1))
death_condition_matrix = (death_years > birth_years.reshape(-1, 1))
overlap_matrix = birth_condition_matrix & death_condition_matrix

overlapping_pairs_indices = np.array(np.where(overlap_matrix)).T
overlapping_pairs_indices = np.column_stack((overlapping_pairs_indices[:, 0], overlapping_pairs_indices[:, 1]))

Wir können somit weniger Paare durchlaufen:

Code: Select all

for i, j in overlapping_pairs_indices: #~30M iterations
if i != j:
artist1 = artist_names[i]
artist2 = artist_names[j]

artist1_data = artist_data[artist1]
artist2_data = artist_data[artist2]
val = process.get_loc_similarity(artist1_data, artist2_data)

if val > 0:
G.add_edge(artist1, artist2, weight=val)

Es ist eine Überraschung, dass dies immer noch über ~13 Minuten läuft – anstatt die Laufzeit um etwa 40 % zu verbessern.
Überraschenderweise ist die Iteration auf den Matrixindizes viel schneller, obwohl alle 50 Millionen Kombinationen berücksichtigt werden:

Code: Select all

for i in range(len(artist_names)):
for j in range(i + 1, len(artist_names)): #~50M iterations
if overlap_matrix[i, j]:
artist1 = artist_names[i]
artist2 = artist_names[j]

artist1_data = artist_data[artist1]
artist2_data = artist_data[artist2]

val = process.get_loc_similarity(artist1_data, artist2_data)

if val > 0:
G.add_edge(artist1, artist2, weight=val)

Dies lief weniger als 5 Minuten, obwohl es noch einmal 50 Millionen Mal iteriert wurde.

Das ist überraschend und vielversprechend, und das würde ich gerne tun Finden Sie heraus, was dies schneller als den vorherigen Versuch macht und wie Sie es so ändern können, dass es noch schneller wird.
Wie kann ich die Laufzeit verbessern, indem ich die richtigen Methoden verwende?

Ich frage mich, ob es eine Möglichkeit einer weiteren Nutzung gibt numpy, z.B. Ich muss keine for-Schleifen verwenden, selbst wenn ich die Berechnungsfunktion aufrufe, sondern verwende stattdessen eine Methode ähnlich der von pandas dataframe .apply().
(Mir ist auch aufgefallen, dass das Durchlaufen einer ZIP-Datei eine Schleife darstellt wie zum Beispiel für i, j in zip(overlap_pairs[:, 0], Overlap_pairs[:, 1]) hat die Laufzeit nicht verbessert.)