python - 与同时使用最小值和最大值相比，此函数同时检索最小值和最大值的速度快吗？

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()时，每一个都必须在iterable上迭代一次。它们分别执行，所以当您需要最小值和最大值时，通过使用内置函数，迭代两次。
你的函数只是在它上面迭代一次，所以它的理论运行时间更短。现在，正如chepter在注释中提到的，min和max是在in native code中实现的，因此它们肯定比用Python代码自己实现时要快。
现在，这在很大程度上取决于iterable的两个本地循环是否比Python函数快。对于较长的列表，迭代它已经很昂贵，迭代一次肯定会更好，但是对于较短的列表，使用本机代码可能会得到更好的结果。我不知道确切的阈值在哪里，但您可以很容易地测试出实际的数据，速度更快。不过，在大多数情况下，最小/最大值并不是应用程序的瓶颈，因此在成为问题之前，您不必担心它。
顺便说一下，您的实现现在有一些问题，如果您想使用它，您应该解决这些问题：
它要求iterable是一个序列，而不是iterable（因为您在它上使用索引）
你还要求它至少有一个技术上不需要的项目。当您检查not iterable时，它不一定告诉您序列/iterable的长度。自定义类型可以轻松地提供自己的布尔值和/或序列行为。
最后，使用iterable项的键控值初始化_min和_max，但稍后您（正确地）只需从iterable中分配原始项。
因此，我建议您改用迭代器，并修复这个键，您还可以存储键结果，从而为更复杂的键函数节省一些计算：

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实现昂贵的原因。这也很有意义。即使使用标识lamba，您仍然有函数调用的开销； len(iterable)许多函数调用（使用上面的优化变量）。函数调用也很昂贵。
在我的测试中，去掉了对键函数的支持，实际的预期结果出现了：只迭代一次比两次快。但对于不太大的iterables来说，差别真的很小。因此，除非迭代iterable非常昂贵（尽管您可以使用 tee并仍然迭代两次），或者您无论如何都想循环它（在这种情况下，您可以将其与min/max检查结合起来），否则单独使用内置的 max()和 min()函数将更快，也更容易使用。而且，它们都带有内部优化功能，如果不指定键函数，它们会跳过键函数。
最后，你怎么能把关键函数优化添加到你的代码中呢？不幸的是，只有一种方法可以做到这一点，那就是复制代码。实际上，您必须检查是否指定了键函数，如果没有指定键函数，则跳过函数调用

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