时间戳

首页 > 解决方案 > Python中过滤的优化

python - Python中过滤的优化

问题描述

我需要can_clump在 python 中的许多对象上运行一个复杂的函数。这需要很长时间才能运行，所以我正在尝试优化。

只有一些对象需要can_clump在它们上面运行，所以我正在尝试过滤。

我目前拥有的解决方案在这里：

for clump1 in stored.clumps:
    for clump2 in stored.clumps:
        if clump1.classification = clump2.classification:
            if clump1.can_clump(clump2):
                #some code here

但我不确定我是否可以结合 if 语句 if an and 来简化它，或者这是否需要 python 到 python 来检查两者：

for clump1 in stored.clumps:
    for clump2 in stored.clumps:
        if clump1.classification = clump2.classification and clump1.can_clump(clump2):
            #some code here

或者，在迭代之前过滤列表甚至可能更快：

for clump1 in stored.clumps:
    for clump2 in filter(lambda x: x.classification == clump1.classification, stored.clumps):
         if clump1.can_clump(clump2):
              #some code here

我不确定哪个更快并且应该实施。

标签： python

解决方案

首先，结合你的两个条件很容易：

for clump1 in stored.clumps:
    for clump2 in stored.clumps:
        if clump1.classification == clump2.classification and clump1.can_clump(clump2):
            #some code here

做你想做的事，它会短路；如果第一次测试失败，can_clump将不会被调用。

其次，作为一项规则，filter当需要 alambda来实现它时，它通常会比较慢；唯一一次看到有意义的节省是谓词本身是用 C 实现的内置函数。如果您已经需要调用现有的 Python 定义的函数，那么filter通常没有好坏之分，因此使用它几乎没有什么坏处.

因此，对于您的情况，假设它classification是内置类型（或 C 扩展实现的类型），您可能可以通过以下方式进行一些优化：

for clump1 in stored.clumps:
    for clump2 in filter(clump1.can_clump, filter(clump1.classification.__eq__, stored.clumps)):
          #some code here

也就是说，这都是微优化。即使它有效，我们谈论的可能是 10% 的加速，如果这是代码中最热门的部分，并且一切正常。通常，担心微优化是浪费时间。99% 的情况下，如果没有它，性能还是不错的，或者无论你是否这样做，性能都会慢得让人无法接受。

在这种情况下，您可能会从对块进行预分组中获得更多收益，减少O(n²)嵌套迭代的工作，stored.clumps这些工作至少可以完成O(n log n)(with sorted+ itertools.groupby) 或O(n)(with a multi-中的一些工作dict，例如collections.defaultdict(list)）。例如，按分类分组的预处理运行可以是：

# Imports at top of file
from collections import defaultdict
from itertools import product

# Code using them
clumps_by_classification = defaultdict(list)

for clump in stored.clumps:
    clumps_by_classification[clump.classification].append(clump)

现在，您可以将子组与匹配的分类进行比较，而不是将每个簇与其他簇进行比较：

for classification, clumps in clumps_by_classification.items():
    for clump1, clump2 in product(clumps, repeat=2):
        if clump1.can_clump(clump2):
            # some code here

根据团块排序是否重要，以及团块是否应该能够与自己结块，您可以通过替换product另一个itertools函数（如combinations、combinations_with_replacement或）来节省更多permutations。

是的，理论上，该product(repeat=2)步骤保留了工作O(n²)，但现在是O(n²)当n是具有相同 的最大子群时classification，而不是就整个丛集而言。

推荐阅读