此功能是否可以比分别使用最小值和最大值同时检索最小值和最大值？

Question

我有一个函数来同时检索列表的最小值和最大值:

def min_max(iterable, key=None):
    """Retrieve the min and max values of `iterable` simultaneously."""
    if key is None: key = lambda x: x
    if not iterable:
        return None, None
    min_ = max_ = key(iterable[0])
    for i in iterable[1:]:
        if key(i) > key(max_): max_ = i
        if key(i) < key(min_): min_ = i
    return min_, max_

但它让我感到疑惑,因为无论如何我在for循环中进行了两次比较min,max单独使用和单独使用会不会更快？如果是,我如何编辑此功能以提高效率？

Answer 1

找出列表中的最小值或最大值的昂贵部分不是比较.比较值非常快,并且不会在这里产生问题.相反,影响运行时间的是循环.

当您使用min()或时max(),其中每个都必须迭代迭代一次.它们分别执行此操作,因此当您需要最小值和最大值时,通过使用内置函数,您将迭代两次.

您的函数只需迭代一次,因此其理论运行时间更短.现在正如注释中提到的那样,min并且max是用本机代码实现的,所以它们肯定比自己在Python代码中实现它更快.

现在,它很大程度上取决于你的迭代是否两个本机循环将比你的Python函数更快.对于更长的列表,迭代它已经很昂贵,迭代它肯定会更好,但对于较短的列表,你可能会使用本机代码获得更好的结果.我无法确定确切的阈值在哪里,但您可以轻松地测试实际数据的速度.但在大多数情况下,它很少会因为min/max不会成为你的应用程序的瓶颈,所以你不应该担心它会成为一个问题.

顺便说一句.你的实现现在有一些问题,如果你想使用它你应该修复:

• 它需要iterable是一个序列,而不是一个可迭代的(当你在它上面使用索引时)
• 您还要求它至少有一个项目 - 技术上也不需要.当您检查时not iterable,这不一定会告诉您有关序列/可迭代的长度的信息.自定义类型可以轻松提供自己的布尔值和/或序列行为.
• 最后,你初始化_min并_max与迭代项目的键值,但以后你(正确)刚刚分配从迭代原始项目.

所以我建议你改用迭代器,并修复那个关键的东西 - 你也可以存储关键结果,以便为更复杂的关键函数保存一些计算:

it = iter(iterable)
try:
    min_ = max_ = next(it)
    minv = maxv = key(min_)
except StopIteration:
    return None, None

for i in it:
    k = key(i)
    if k > maxv:
        max_, maxv = i, k
    elif k < minv:
        min_, minv = i, k

我做了一些测试,事实证明 - 没有自定义键功能 - 使用内置的max/min是不可能的.即使对于非常大的列表,purce C实现也太快了.但是,只要添加一个键函数(用Python代码编写),情况就会完全颠倒过来.使用键功能,您可以获得与单个min或max调用完全相同的时序结果,以及完成两个功能的完整功能.因此,使用Python编写的解决方案要快得多.

因此,这导致了这样的想法,也许,Python中的实现不是实际问题,而是使用的key函数.事实上,实际的关键功能是使Python实现成本高昂的原因.它也很有道理.即使使用identity-lamba,你仍然有函数调用的开销; len(iterable)许多函数调用(使用上面的优化变体).功能调用非常昂贵.

在我的测试中,由于支持关键功能,实际预期的结果出现了:迭代一次比两次快.但对于非常大的迭代,差异非常小.因此,除非迭代迭代是非常昂贵的(尽管你可以使用tee并仍然迭代两次)或者你想要循环它(在这种情况下你将它与min/max检查结合),使用内置max()和min()函数分开将更快,也更容易使用.并且,如果您没有指定关键功能,它们都会进行内部优化.

最后,您如何在代码中添加关键函数优化？好吧,不幸的是,只有一种方法可以做到这一点,这涉及到复制代码.您基本上必须检查是否指定了键功能,并在不执行时跳过函数调用.所以,像这样:

def min_max(iterable, key=None):
    if key:
        # do it with a key function
    else:
        # do it without