Альтернатива этому коду Python?

У меня есть строка кода из класса, которую я не понимаю полностью и хочу более легкую альтернативу. Для этого используется weightList, представляющий собой список ребер, связанных друг с другом, и возвращает списки ребер с наименьшим соответствующим значением из графа (матрица смежности). Это для задачи Prim's Minimum Spanning Tree.

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

Источник

4 ответа

Решение

Разбить его немного может быть достаточно. Как насчет этого?

get_edge_weight = lambda e: graph[e[0]][e[1]]
sorted_weights = sorted(weightList, key=get_edge_weight)
edge = sorted_weights[0]
Источник

Сделайте точно так, как вы сказали: для всех ребер найдите на графике значение, которое является самым низким.

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, которая является функцией, которая возвращает значение. В вашем случае ваша функция возвращает значение в graph в положении вашего края. sorted будет использовать это значение, чтобы сравнить края вместе.

Таким образом, это отсортирует все ваши ребра от одного с самым низким значением до того, которое имеет самое высокое значение. Затем, как только он отсортирован, вы берете первый элемент, который является ребром с наименьшим значением.

Алгоритмически, используя sorted для этой работы не очень хорошая идея, так как она имеет временную сложность O(n log n), Для сравнения, мой алгоритм O(n) (но, вероятно, медленнее, потому что я предполагаю, sorted реализовано в C). Вместо этого вы можете получить тот же результат в O(n) используя стандартные функции с помощью min что, безусловно, является наиболее эффективным и читаемым вариантом из всех трех:

edge = min(weightList, key=lambda (i,j): graph[i][j])
Источник

Пытаясь уменьшить сложность, я всегда ищу способы разбить вещи на понятные, модульные функции:

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];
Источник

Если вы хотите, чтобы код был немного менее "компактным", это должно сработать:

shortest = weightList[0]

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

Установите самое короткое ребро равным первому ребру в weightList, затем просмотрите список и посмотрите, короче ли какие-нибудь ребра.

Источник
Другие вопросы по тегам