python - 查找最大值或最小值的键

Question

max和 min函数对每个元素只计算一次 key 参数，这是我从 list.sort 的文档中推断出来的他们提到的(以及对其实现的有根据的猜测):

The key corresponding to each item in the list is calculated once and then used for the entire sorting process.

这意味着使用不总是为给定输入返回相同输出的键函数应该是安全的。但是是否可以在不自定义函数或再次调用键函数的情况下优雅地检索最大值或最小值的键？

对于非确定性 key ，以下方法不起作用:

max_val = max(iterable, key=key)
max_key = key(max_val)

同样的问题发生在

max_val = sorted(iterable, key=key)[0]

自定义函数可以这样写:

from itertools import tee
def max_and_key(iterable, *, key=None):
    i1, i2 = tee(iterable)
    max_val = max(k, -i, v for i, (k, v) in enumerate(zip(map(key, i1), i2)))
    return max_val[2], max_val[0]

tee有必要使这项工作适用于任意可迭代对象，其中 zip 的元素必须在不相互干扰的情况下处理可迭代对象的相同元素。 zip 确保 tee 一次不必存储多个元素，以最大限度地减少计算的惰性。 Enumeration确保对于键相同但值不同的情况，以与原始函数一致的方式保持比较的稳定性:

If multiple items are maximal [minimal], the function returns the first one encountered.

注意被最大化的表达式中的减号。

总而言之，这个函数对于检索已经在计算的东西来说似乎是一种过大的杀伤力。对此有更好的解决方案吗？

如果没有别的办法，至少这个函数和max有同样的算法复杂度和一般契约。

切线/奖金问题:形容词是什么意思“不是每次都为相同的输入返回相同的结果”？不确定性只是可能性的一小部分，不可重入意味着与我的理解略有不同。

Answer 1

为此，您需要预先计算 key 。将键/值放在元组中可能最有意义。但是，您需要注意 min/max/sort 只对键而不是值进行比较(否则如果值不可比较，如果有重复的键，这将失败):

from operator import itemgetter

def max_with_key(iterable, key):
    """
    Returns a (max_key, max_value) tuple by applying max to the iterable with
    the given key. Useful in cases when the key function is non-deterministic
    and the original key used in the max operation is desired.

    >>> from random import randint
    >>> max_with_key([1, 2, 3], key=lambda _: randint(0, 10))
    (9, 3)
    >>> max_with_key([1, 2, 3], key=lambda _: randint(0, 10))
    (8, 1)
    """
    prekeyed = ((key(x), x) for x in iterable)
    return max(prekeyed, key=itemgetter(0))