在Python列表中查找使函数最大化/最小化的所有元素的最快方法

Question

让我们用一个简单的例子:假设我有一个列表的列表

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]

和我想找到所有最长的列表，也就是所有使len函数最大化的列表。当然可以

def func(x):
return len(x)
maxlen = func(max(ll, key=lambda x: func(x)))
res = [l for l in ll if func(l) == maxlen]
print(res)

输出

[[1, 2, 3], [2, 3, 4]]

但是我想知道是否有更有效的方法来做到这一点，特别是当函数非常昂贵或列表非常长时。有什么建议吗?

Answer 1

从计算机科学/算法的角度来看，这是一个非常经典的"还原"。问题。

所以,伪代码。这真的很简单。

metric():= a mapping from elements to non-negative numbers
winner = []
maxmetric = 0
for element in ll:
if metric(element) larger than maxmetric:
winner = [ element ]
maxmetric = metric(element)
else if metric(element) equal to maxmetric:
append element to winner

Answer 2

当函数非常昂贵时

请注意，您为每个元素计算两次func(x)，首先是

maxlen = func(max(ll, key=lambda x: func(x)))

,

res = [l for l in ll if func(l) == maxlen]

所以存储已经计算过的内容是有益的。functools.lru_cache允许轻松地替换

def func(x):
return len(x)

使用

import functools
@functools.lru_cache(maxsize=None)
def func(x):
return len(x)

然而，要注意，由于数据存储的方式，参数必须是可哈希的，所以在你的例子中，你首先需要将列表转换为tuples，即

ll = [(1, 2), (1, 3), (2, 3), (1, 2, 3), (2, 3, 4)]

参见文档中的描述以获得进一步的讨论

Answer 3

不能像下面这样使用dictionary，(这是O(n))

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]
from collections import defaultdict
dct = defaultdict(list)
for l in ll:
dct[len(l)].append(l)

dct[max(dct)]

输出:

[[1, 2, 3], [2, 3, 4]]

>>> dct
defaultdict(list, {2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]})

或者使用setdefault而不使用defaultdict，如下所示:

ll = [[1, 2], [1, 3], [2, 3], [1, 2, 3], [2, 3, 4]]
dct = {}
for l in ll:
dct.setdefault(len(l), []).append(l)

输出:

>>> dct
{2: [[1, 2], [1, 3], [2, 3]], 3: [[1, 2, 3], [2, 3, 4]]}