Alternative zu diesem Python-Code?

Question

Ich habe eine Reihe von Code aus der Klasse, die ich nicht vollständig verstehe und eine einfachere Alternative zu wollen. Was dies tut, verwendet WeightList, eine Liste von Kanten, die miteinander verbunden sind, und gibt die Kantenlisten mit dem niedrigsten entsprechenden Wert aus dem Graphen (Adjazenzmatrix) zurück. Dies ist für ein Minimum-Spanning-Tree-Problem von Prim.

edge = sorted(weightList, key=lambda e:graph[e[0]][e[1]])[0];

Answer 1

Brechen es ein wenig könnte genug sein. Wie wäre es damit?

Answer 2

Tun Sie genau wie Sie gesagt haben: für alle Kanten, finden Sie den Wert in der Grafik, die die niedrigste ist.

i, j = current_edge = weightList[0] 
current_min = graph[i][j] 

for edge in weightList[1:]: 
    i, j = edge 

    if graph[i][j] < current_min: 
     current_min = graph[i][j] 
     current_edge = edge 

Sie beginnen mit der ersten Flanke von Ihrem weightList, dann wiederholen Sie an allen anderen Kanten Wert zu versuchen und zu finden, das niedriger ist. Wenn Sie die Schleife verlassen, ist current_edge die Kante mit dem niedrigsten Wert.

Davon abgesehen, könnte es sich lohnen, stattdessen zu versuchen, Ihren Code zu verstehen. Ich nehme an, Sie wissen, was sorted tut. Um Ihre weightList zu sortieren, verwendet sorted den Parameter key, eine Funktion, die einen Wert zurückgibt. In Ihrem Fall gibt Ihre Funktion den Wert in an der Position Ihrer Kante zurück. sorted wird diesen Wert verwenden, um die Kanten miteinander zu vergleichen.

Damit werden alle Ihre Kanten von dem mit dem niedrigsten Wert zu dem mit dem höchsten Wert sortiert. Dann, sobald es sortiert ist, nehmen Sie das erste Element, das ist die Kante mit dem niedrigsten Wert.

Algorithmisch, mit sorted für diesen Job ist keine gute Idee, da es eine Zeit Komplexität von O(n log n) hat. Im Vergleich dazu ist mein Algorithmus O(n) (aber wahrscheinlich langsamer, weil ich annehme sorted ist in C implementiert). Stattdessen können Sie das gleiche Ergebnis in O(n) unter Verwendung von Standard-Funktionen unter Verwendung min, erhalten, die sicher ist die effizienteste und lesbar Option aus allen drei:

edge = min(weightList, key=lambda (i,j): graph[i][j]) 

Answer 3

Wenn Sie den Code ein bisschen weniger „kompakt zu sein “, sollte dies den Trick:

shortest = weightList[0] 

for edge in weightList: 
    if graph[edge[0]][edge[1]] < graph[shortest[0]][shortest[1]]: 
     shortest = edge 

die kürzeste Kante gleich die ersten Kante zu sein in dem weightList, dann durch die Liste gehen und sehen, ob irgendwelche Kanten kürzer sind.

Answer 4

Wenn die Komplexität zu reduzieren versuchen, ich nach Wegen suchen, die Dinge immer in selbsterklärend modulare Funktionen, auszubrechen:

def distance(adjacency_matrix, start_node, end_node): 
    return adjacency_matrix[start_node][end_node] 

sorted_edges = sorted(weightList, key=lambda e: distance(graph, e[0], e[1])) 
edge = sorted_edges[0];