优化复杂的列表理解语句

Question

如何优化Step 3中的列表理解语句？

背景：

在现实世界中：

r 包含大约 ~500 个元素并且
a 包含大约 100 万个元素

请注意 Step 3 是 r 和 a 的嵌套循环。因此，这需要很多时间。在下面的代码中，为了简单起见，r 和 a 被缩短了。

我还提到这个函数 some_heavy_calculation() 作为背景。这个函数这里就不透露了，不过因为也是调用了len(r) * len(a)次，所以也很耗时间

为了加快速度，我注意到通过引入“更快”的替代方案，我可以避免对 some_heavy_calculation() 的所有调用中的 90-95%。唯一的问题是 Step 3 现在需要很多时间。事实上，这一步消耗的时间比我能节省的还要多。

def some_heavy_calculation(rules, data) -> list:
    # ...
    return []

# r = input rules
r =  ['x', 'y', 'z']

# a = input data
a =  [7,     7,     7,     4,     4,     2,     2,     8,     2,     9,     4,     4,     8,     7    ]

#########
# Slow alternative: b = result of some_heavy_calculation(r, a)
# b = expected result, size: [ r x a ]
b = [[True,  True,  True,  True,  True,  True,  True,  True,  True,  False, True,  True,  True,  True],
     [True,  True,  True,  False, False, True,  True,  True,  True,  False, False, False, True,  True],
     [False, False, False, True,  True,  False, False, True,  False, False, True,  True,  True,  False]]
#########

#########
# Faster:
# Since these steps avoids 90-95 % of all the calls to some_heavy_calculation()
#
# Step 1: c = a in order, but without duplicates
c =  [7,                   4,            2,            8,            9                                ] 

# Step 2: d = result of calculation, size: [ r x c ]
d = [[True,                True,         True,         True,         False                            ],
     [True,                False,        True,         True,         False                            ],
     [False,               True,         False,        True,         False                            ]]

# Step 3: e = should equal b
e = [[d[ri][next(ci for ci, cv in enumerate(c) if cv == av)] for ai, av in enumerate(a)] for ri, rv in enumerate(r)]
#########

str(b) == str(e) # <--- returns True

Answer 1

在我看来，您需要的是一种名为 memoization 的模式。

有一个 functools.cache decorator (for Python < 3.9 you can use lru_cache) 可以这样使用：

import functools

@functools.cache
def some_heavy_calculation_per_item(rules, value) -> bool:
    # ...
    return []

def some_heavy_calculation(rules, data) -> list:
    # ...
    returned = []
    for value in data:
        returned.append(some_heavy_calculation_per_item(rules, value))

    return returned

使用记忆化可以有效地对每个值进行一次计算（如您所述，可节省 90-95%），而且可以节省内存（无需组合许多大型列表或数组）。

另一个潜在的优化是使用 yield 而不是在 some_heavy_calculation 函数中构造列表，但这取决于您使用结果的方式 - 如果按值计算，则 yielding将提高性能。如果您需要完整的列表 - 那么它根本无济于事。

优化复杂的列表理解语句

Optimizing a complex list comprehension statement

python

algorithm

performance

list-comprehension

list