Есть ли способ написать лучше "max_degree"?

Question

Полагаю, так как я новичок в Python.

Мне дали несколько доставок, одна из которых была: " Учитывая график, найдите узел (ы) с максимумом Степень и вернуть его / их в списке."

Мое решение:

def max_degree(graph):
    """
    :param graph: non-null and non-oriented networkx type graph to analyze.
    :return: list of nodes of this graph with maximum degree; 0 if the graph has no nodes; -1 if the graph is disconnected;
    """
    if len(graph.nodes) == 0:
        return 0
    if not nx.is_connected(graph):
        return -1
    # node_grade_list -> [(<node>, <grade>), ...]
    node_grade_list = sorted(grafo.degree, key=lambda x: x[1], reverse=True)
    max_grade = node_grade_list[0][1]
    max_grade_nodes_list = []
    for node in node_grade_list:
        if node[1] == max_grade:
            max_grade_nodes_list.append(node[0])
    return max_grade_nodes_list

Я хотел бы спросить вас: Есть ли способ сделать его намного более эффективным? Я сильно бьюсь головой, но не могу найти другие более «удобные» маршруты. Я принимаю любой код, спасибо.

Answer 1

Предполагая, что graph.degree является списком кортежей

[(<node>, <grade>), ...]

Заменить получение макс. Узлов на

max_grade = max(graph.degree, key=lambda x: x[1])[1]
max_grade_nodes_list = [node[0] for node in graph.degree if node[1] == max_grade]

Это быстрее, так как это O ( n), в то время как сортировка требует O (n * log (n))

Пересмотренный код

def max_degree(graph):
    """
    :param graph: non-null and non-oriented networkx type graph to analyze.
    :return: list of nodes of this graph with maximum degree; 0 if the graph has no nodes; -1 if the graph is disconnected;
    """
    if len(graph.nodes) == 0:
        return 0
    if not nx.is_connected(graph):
        return -1
    # graph.degree -> [(<node>, <grade>), ...]
    max_grade = max(graph.degree, key=lambda x: x[1])[1]

    return [node[0] for node in graph.degree if node[1] == max_grade]

Объяснение того, почему Макс быстрее

Сложность времени - это понятие в компьютерной науке, которое имеет дело с количественной оценкой количества времени, затрачиваемого набором кода или алгоритмом на обработку или выполнение, как функция количества ввода.

И max, и отсортированные являются встроенными функциями, поэтому обе имеют естественную кодировку.

Функция max является линейной по времени O (n), поскольку нам нужно только пройти по списку один раз, чтобы найти максимум , Это означает, что, поскольку мы удваиваем размер n списка, время, необходимое для нахождения максимального значения удваивается.

Python сортировка использует TimSort , которая имеет среднюю сложность времени O (n * log (n)), где n - длина входного списка.

O (n * log (n)): средняя сложность типична для многих алгоритмов сортировки, таких как быстрая сортировка, mergesort и т. д. c .

Сравнивая O (n * log (n)) с O (n), мы видим, что Макс имеет преимущество в скорости:

O(n*log(n))/log(n)  = O(log(n)).

Значение для списка из 1024 элементов, n = 2 ^ 10 будет лог (2 ^ 10) = в 10 раз быстрее

Для меньшего списка, например n = 10, не будет иметь значения, какой метод вы используете.