이 python 코드에 대체 하시겠습니까?

Question

나는 완전히 이해하지 못하는 클래스의 코드를 가지고 있으며 좀 더 쉬운 대안을 원합니다. 이 기능은 서로 연결된 가장자리 목록 인 weightList를 사용하고 그래프에서 해당 값이 가장 낮은 edgelists (인접성 행렬)를 반환합니다. 이것은 Prim의 Minimum Spanning Tree 문제입니다.

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

Answer 1

조금 그것을 깨는 것은 충분히있을 수 있습니다. 이건 어때?

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

Answer 2

모든 말풍선에 대해 가장 낮은 그래프의 값을 찾으십시오.

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 

당신은 당신이 시도하고 낮은 값을 찾기 위해 다른 모든 가장자리에 반복하여 weightList에서 최초의 가장자리로 시작합니다. 루프를 종료하면 current_edge이 가장 낮은 값의 가장자리입니다.

그렇다면 코드를 시도하고 이해하는 것이 가치가있을 수 있습니다. sorted이 무엇인지 알고 있다고 가정합니다. weightList을 정렬하기 위해 sorted은 값을 반환하는 함수 인 key을 사용합니다. 귀하의 경우 귀하의 함수는 의 값을 귀하의 가장자리에서 반환합니다. sorted은이 값을 사용하여 가장자리를 서로 비교합니다.

따라서 가장 낮은 값을 가진 에지부터 가장 높은 값을 갖는 에지를 모두 정렬합니다. 그런 다음 일단 정렬되면 가장 낮은 값의 가장자리 인 첫 번째 요소를 가져옵니다.

알고리즘으로이 작업에 sorted을 사용하는 것은 시간 복잡성이 O(n log n)이므로 좋은 생각이 아닙니다. 비교해 보면, 내 알고리즘은 O(n)입니다 (하지만 sorted이 C로 구현되어 있기 때문에 속도가 느려질 수 있습니다). 대신, 당신은 확실히 가장 효율적이고 읽을 수있는 옵션이 세 가지 모두를 벗어 min를 사용하여 표준 기능을 사용하여 O(n)에서 같은 결과를 얻을 수 있습니다

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

Answer 3

당신은 코드가 좀 덜 "컴팩트하려면 weightList의 첫 번째 에지 동일하게 짧은 가장자리를 설정

shortest = weightList[0] 

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

는 다음 목록을 통해 이동하고 가장자리가 짧은 경우 참조 : "이 트릭을 할해야합니다.

Answer 4

복잡성을 감소하려고 할 때, 난 항상 자기 설명에 물건을 깰 방법을 찾고, 모듈 형 기능 :

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];