python - 使用许多属性和字典查找优化 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

如何保持 interaction_graph.neighbors_iter(node) 的迭代顺序排序(或使用 collections.heapq 部分排序)？由于您只是想找到最大值，因此可以按降序迭代 node_neighbors，selected_node 中的第一个节点必须是 selected_node 中的最大值。

其次，selected_node多久改变一次？如果它很少更改，您可以通过使用“interaction_graph.node[neighbor] for x in selected_node”列表来节省大量迭代，而不必每次都重建此列表。

编辑:回复评论

A sort() would take O(n log n)

不一定，您看的课本太多了。不管您的教科书怎么说，您有时都可以通过利用数据的特定结构来打破 O(n log n) 障碍。如果您首先将邻居列表保存在自然排序的数据结构中(例如 heapq、二叉树)，则不需要在每次迭代时都重新排序。当然，这是一种时空权衡，因为您需要存储冗余的邻居列表，并且存在代码复杂性以确保在邻居更改时更新邻居列表。

此外，python 的 list.sort()，它使用 timsort算法，对于几乎排序的数据非常快(在某些情况下可以平均 O(n))。它仍然没有打破 O(n log n)，这已被证明在数学上是不可能的。

您需要在排除不太可能提高性能的解决方案之前进行分析。在进行极端优化时，您可能会发现在某些非常特殊的边缘情况中，旧的和缓慢的冒泡排序可能会胜过美化的快速排序或归并排序。