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

Question

Я написал программу на Python, которая тратит много времени на поиск атрибутов объектов и значений из словарных ключей. Я хотел бы знать, можно ли каким-либо образом оптимизировать это время поиска, возможно, с помощью расширения C, чтобы сократить время выполнения, или мне нужно просто повторно реализовать программу на скомпилированном языке.

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

Выражение генератора в строке 202 равно

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

и выражение генератора в строке 204 равно

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

Исходный код для этой функции контекста представлен ниже.

selected_nodes - это set узлов в interaction_graph, который является NetworkX Graph экземпляром. node_neighbors является итератором от Graph.neighbors_iter().

Graph сам использует словари для хранения узлов и ребер. Его атрибут Graph.node представляет собой словарь, в котором хранятся узлы и их атрибуты (например, 'weight') в словарях, принадлежащих каждому узлу.

Каждый из этих поисков должен амортизироваться постоянным временем (т. Е. O (1)), однако я все еще плачу большой штраф за поиски. Есть ли какой-нибудь способ ускорить поиск (например, записав его части как расширение C) или мне нужно переместить программу на скомпилированный язык?

<ч />

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

def calculate_node_z_prime(
        node,
        interaction_graph,
        selected_nodes
    ):
    """Calculates a z'-score for a given node.

    The z'-score is based on the z-scores (weights) of the neighbors of
    the given node, and proportional to the z-score (weight) of the
    given node. Specifically, we find the maximum z-score of all
    neighbors of the given node that are also members of the given set
    of selected nodes, multiply this z-score by the z-score of the given
    node, and return this value as the z'-score for the given node.

    If the given node has no neighbors in the interaction graph, the
    z'-score is defined as zero.

    Returns the z'-score as zero or a positive floating point value.

    :Parameters:
    - `node`: the node for which to compute the z-prime score
    - `interaction_graph`: graph containing the gene-gene or gene
      product-gene product interactions
    - `selected_nodes`: a `set` of nodes fitting some criterion of
      interest (e.g., annotated with a term of interest)

    """
    node_neighbors = interaction_graph.neighbors_iter(node)
    neighbors_in_selected_nodes = (neighbor for neighbor in
            node_neighbors if neighbor in selected_nodes)
    neighbor_z_scores = (interaction_graph.node[neighbor]['weight'] for
            neighbor in neighbors_in_selected_nodes)
    try:
        max_z_score = max(neighbor_z_scores)
    # max() throws a ValueError if its argument has no elements; in this
    # case, we need to set the max_z_score to zero
    except ValueError, e:
        # Check to make certain max() raised this error
        if 'max()' in e.args[0]:
            max_z_score = 0
        else:
            raise e

    z_prime = interaction_graph.node[node]['weight'] * max_z_score
    return z_prime

Вот пара лучших звонков по cProfiler, отсортированная по времени.

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
156067701  352.313    0.000  642.072    0.000 bpln_contextual.py:204(<genexpr>)
156067701  289.759    0.000  289.759    0.000 bpln_contextual.py:202(<genexpr>)
 13963893  174.047    0.000  816.119    0.000 {max}
 13963885   69.804    0.000  936.754    0.000 bpln_contextual.py:171(calculate_node_z_prime)
  7116883   61.982    0.000   61.982    0.000 {method 'update' of 'set' objects}

Answer 1

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

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

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

Для сортировки () потребуется O (n log n)

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

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

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

Answer 2

Я не понимаю, почему ваши "весовые" поиски должны иметь форму ["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)

Answer 3

Не углубляясь в ваш код, попробуйте добавить немного скорости с 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)
    )
)

Это помогает?

Answer 4

Попробуйте просто получить прямой доступ к 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)