Оптимизация кода Python с помощью множества поисковых запросов по атрибутам и словарям

Как насчет того, чтобы отсортировать (или частично отсортировать с помощью collections.heapq) порядок итераций для interface_graph.neighbors_iter(node)? Поскольку вы просто пытаетесь найти максимальное значение, вы можете перебирать node_neighbors в порядке убывания, первый узел, который находится в selected_node, должен быть максимальным в selected_node.

Во-вторых, как часто будет меняться selected_node? Если он меняется редко, вы можете сэкономить много итераций, имея список «interaction_graph.node[neighbor] для x в selected_node», вместо того, чтобы каждый раз перестраивать этот список.

РЕДАКТИРОВАТЬ: чтобы ответить на комментарии

sort() будет принимать O (n log n)

Не обязательно, вы слишком много смотрите в свой учебник. Несмотря на то, что написано в вашем учебнике, вы иногда можете преодолеть барьер O(n log n), используя определенную структуру ваших данных. Если вы храните свой список соседей в естественно отсортированной структуре данных в первую очередь (например, heapq, двоичное дерево), вам не нужно повторно сортировать на каждой итерации. Конечно, это компромисс между пространством и временем, поскольку вам нужно будет хранить избыточные списки соседей, и существует сложность кода, чтобы гарантировать, что список соседей обновляется при изменении соседей.

Кроме того, python list.sort(), который использует алгоритм timsort, очень быстр для почти отсортированных данные (в некоторых случаях может усреднить O (n)). Он по-прежнему не ломает O (n log n), так как было доказано, что это математически невозможно.

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

Я не понимаю, почему ваш поиск по «весу» должен быть в форме ["weight"] (узлы — это словари?) вместо .weight (узлы — это объекты).

Если ваши узлы являются объектами и не имеют большого количества полей, вы можете воспользоваться преимуществом директива __slots__ для оптимизации их хранения:

class Node(object):
    # ... class stuff goes here ...

    __slots__ = ('weight',) # tuple of member names.

РЕДАКТИРОВАТЬ: Итак, я просмотрел предоставленную вами ссылку NetworkX, и есть несколько вещей, которые меня беспокоят. Во-первых, прямо вверху определение «словарь» — «FIXME».

В целом кажется, что для хранения атрибутов настойчиво используются словари, а не классы, которые могут быть подклассами. Хотя поиск по атрибутам объекта может по существу быть поиском по словарю, я не вижу, чем работа с объектом может быть хуже. Во всяком случае, это может быть лучше, поскольку поиск атрибутов объекта с большей вероятностью будет оптимизирован, потому что:

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

Например, я часто использую __slots__ в классах, представляющих координаты. Узел дерева показался бы мне еще одним очевидным применением.

Вот почему, когда я читаю:

узел
Узел может быть любым хешируемым объектом Python, кроме None.

Я думаю, ладно, без проблем, но тут же следует

атрибут узла
Узлы могут иметь произвольные объекты Python, назначаемые в качестве атрибутов с использованием пар ключевое слово/значение при добавлении узла или назначении в словарь атрибутов G.node[n] для указанного узла n.

Я думаю, если узлу нужны атрибуты, зачем хранить их отдельно? Почему бы просто не поместить его в ноду? Вреден ли написание класса с contentString и weight участниками? Края кажутся еще более безумными, поскольку они должны быть кортежами, а не объектами, которые вы могли бы подклассировать.

Так что я немного запутался в дизайнерских решениях, лежащих в основе NetworkX.

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

Наконец, что, если вы объедините свои генераторы:

neighbor_z_scores = (interaction_graph.node[neighbor]['weight'] for
        neighbor in node_neighbors if neighbor in selected_nodes)

Попробуйте просто напрямую получить доступ к dict и поймать KeyErrors, это может быть быстрее в зависимости от вашего соотношения попаданий/промахов:

# cache this object
ignode = interaction_graph.node
neighbor_z_scores = []
for neighbor in node_neighbors:
    try:
        neighbor_z_scores.append(ignode[neighbor]['weight'])
    except KeyError:
        pass

или с getdefault и пониманием списка:

sentinel = object()
# cache this object 
ignode = interaction_graph.node

neighbor_z_scores = (ignode[neighbor]['weight'] for neighbor in node_neighbors)
# using identity testing, it's slightly faster
neighbor_z_scores = (neighbor for neighbor in neighbor_z_scores if neighbor is not sentinel)

Не вникая глубоко в свой код, попробуйте добавить немного скорости с помощью itertools.

Добавьте их на уровне модуля:

import itertools as it, operator as op
GET_WEIGHT= op.attrgetter('weight')

Изменять:

neighbors_in_selected_nodes = (neighbor for neighbor in
        node_neighbors if neighbor in selected_nodes)

в:

neighbors_in_selected_nodes = it.ifilter(selected_node.__contains__, node_neighbors)

а также:

neighbor_z_scores = (interaction_graph.node[neighbor]['weight'] for
        neighbor in neighbors_in_selected_nodes)

в:

neighbor_z_scores = (
    it.imap(
        GET_WEIGHT,
        it.imap(
            interaction_graph.node.__getitem__,
            neighbors_in_selected_nodes)
    )
)

Эти помогают?