Python - 使用 min(list, key=func) 的最小元组列表如何提高效率

Question

给定元组模板列表(region, calc_3d_harmonics(region))，其中calc_3d_harmonics是返回每个区域签名的函数，我需要找到分数最小的区域(实际分数并不重要)。

区域的分数由 calc_harmonics_distance(calc_3d_harmonics(region),query_harmonics, radius) 给出，该函数计算给定半径的两个谐波特征之间的距离(query_harmonics 和 radius 是预先计算的) )。

我当前的解决方案是:

query_harmonics = calc_3d_harmonics(query_region)
ref_region, score = min(templates, key=lambda t: calc_3d_harmonics_distance(t[1], query_harmonics, radius))

团队成员建议我改用以下内容:

query_harmonics = calc_3d_harmonics(query_region)
ref_region, score = min([(t[0], calc_harmonics_distance(t[1], query_harmonics, radius)) for t in templates], key=lambda x: x[1])

注意:calc_3d_harmonics 和 calc_harmonics_distance 都是非常慢且繁重的函数。另外，score 可以替换为 _。

他声称他的建议可能会带来更好的运行时间(尽管这并不重要，因为谐波函数是主要运算)。如果 min(list, key=func) 创建一个 key 列表，那么我们的版本是等效的(而且我的版本更短)，但如果每次他认为我的版本会更慢时都计算 key 。

哪种方式更快？我认为必须有一种更好的(运行时方面的)方法来做到这一点(也许使用 numpy？)并且想听听一些建议。

Answer 1

min(lst, key=func) 对 lst 的每个项目调用一次 func(这也适用于max、list.sort 和 sorted)。因此，如果 lst 包含重复项，则键函数会执行不必​​要的工作，除非您使用内存键函数。

为了说明这一点，这里有几个关键函数，它们在调用时打印它们的参数。 kf 是一个普通的按键函数，kf_cached 使用默认的可变字典来进行内存。

def kf(n):
    print(' Key', n)
    return int(n)

def kf_cached(n, cache={}):
    if n in cache:
        print(' Cached', n)
        return cache[n]
    print(' Key', n)
    cache[n] = k = int(n)
    return k

a = '14142'

u = max(a, key=kf)
print('max', u, '\n')

u = max(a, key=kf_cached)
print('max', u)

输出

 Key 1
 Key 4
 Key 1
 Key 4
 Key 2
max 4 

 Key 1
 Key 4
 Cached 1
 Cached 4
 Key 2
max 4