代码之家 › 专栏 › 技术社区 › Mad Physicist

查找最大值或最小值的键

python-3.x python

Mad Physicist · 技术社区 · 7 年前

这个 max 和 min 函数评估 key 参数对于每个元素只有一次,我从 list.sort 他们提到的(以及对其实现的有根据的猜测):

列表中每个项目对应的键计算一次,然后用于整个排序过程。

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

对于非确定性密钥,以下操作不起作用:

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 有必要对任意iterables进行此操作,其中 zip 必须在不相互干扰的情况下处理iterable的相同元素。这个 拉链 确保 T形三通 一次不必存储多个元素,以实现评估中的最大惰性。 Enumeration 确保在键相同但值不同的情况下,以与原始功能一致的方式保持比较的稳定性:

如果多个项是最大[最小],则函数返回遇到的第一个项。

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

总而言之,这个函数对于检索已经在计算的内容来说似乎是一种巨大的过度使用。有没有更好的解决方案?

如果没有其他方法,至少此函数具有与 最大值 。

相切/额外问题:形容词的意思是“每次对相同的输入不返回相同的结果”是什么?不确定性只是可能性的一小部分,不可重入性在我的理解中意味着微妙的不同。

3 回复 | 直到 7 年前

Bailey Parker 7 年前

为此,您需要预计算密钥。将键/值放在元组中可能最有意义。但是,您需要注意 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))

wim 7 年前

使用元组词典排序如何:

max_key, max_val = max((key(val), val) for val in iterable)

如果数值不可比较,建议 comments :

max_key, _, max_val = max((key(val), -i, val) for i, val in enumerate(iterable))

如果keyfunc的结果是可散列的:

d = {key(x): x for x in iterable}  # note: last value wins for ties
max_key = max(d)
max_val = d[max_key]

Alain T. 7 年前

我认为这也应该奏效:

max(((key(x),x) for x in iterable),key=lambda kx:kx[0])