这个函数同时检索最小值和最大值，是否比分别使用最小值和最大值的方式更快？

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不是更快吗？如果是的话，我该如何编辑这个函数使其更高效呢？

- user3398620

---

你假设iterable至少有一个键。否则，这将在min_ = max_...调用时失败。 - Ian Clark

你为什么要使用一个只返回参数的函数来访问值？ - thefourtheye

权衡之处在于 Python 级别上对列表进行一次遍历与 C 级别上进行两次遍历。哪种方法更快可能取决于列表的长度，但我认为除了极大的列表外，后者都会更快。进行性能分析并查看结果。 - chepner

你能不能把第二个最小值检查改成 elif 呢？ - Ian Clark

一次遍历算法可能具有适用于任意可迭代对象的显著优势，但使用 iterable[0] 和 iterable[1:] 取消了这种优势。 - user2357112

Answer 1

在查找列表中的最小值或最大值时，昂贵的部分不是比较。比较值非常快，不会造成问题。相反，影响运行时间的是循环。

当使用min()或max()时，每个函数都必须对可迭代对象进行一次迭代。它们单独执行，因此当您需要最小值和最大值时，通过使用内置函数，您将进行两次迭代。

您的函数只需对其进行一次迭代，因此其理论运行时间更短。现在，如评论中所提到的，min和max是在本地代码中实现的，因此它们肯定比自己在Python代码中实现要快。

现在，对于你的可迭代对象而言，两个本地循环是否比你的Python函数更快很大程度上取决于它。对于较长的列表，其中迭代已经很昂贵，只需迭代一次就肯定会更好，但对于较短的列表，你可能会获得更好的结果与本地代码。我无法确定确切的阈值在哪里，但你可以轻松测试出实际数据哪个更快。然而，在大多数情况下，这很少有影响，因为最小/最大值不会成为应用程序的瓶颈，所以在它成为问题之前，你不必担心它。

---

顺便说一下，您的实现目前存在一些问题，如果您想使用它，应该进行修复：

• 它要求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函数是无法击败的。即使对于非常大的列表，纯C实现也太快了。但是，一旦添加了一个键函数（用Python代码编写），情况就完全颠倒了。使用键函数时，单个min或max调用的时间结果与执行两者的完整函数几乎相同。因此，使用Python编写的解决方案要快得多。

这导致了这样一个想法，即Python中的实现可能不是真正的问题，而是使用的key函数。实际上，确实是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

- poke

---

我不是那个给你点踩的人，但我想指出一下，认为只迭代一次对于长列表来说比迭代两次更快的想法是误导性的。两种算法都是O(N)，因此它们的相对速度应该保持不变，无论输入的大小如何。这可能只在输入相当大的情况下才成立（以克服可能不同的常量开销），但从10000个项目到1000000个项目的转变不应该对它们的相对性能产生太大影响。 - Blckknght

@Blckknght 当然，它们在O符号中被认为是相等的，但它们仍然具有不同的执行时间，这在优化代码时通常很重要。如果您在应用程序中反复计算最小值和最大值，则可能希望对此进行微调并选择更快的那个，即使两个都是O(n)。如果您阅读了我的答案，您会发现，虽然我指出了差异，但我实际上建议使用单独的函数，因为微优化通常是不必要的。 - poke

Answer 2

简述

如果输入是NumPy数组，请参见这里。

如果输入是一个序列：

• min()和max()通常比手动循环更快（除非使用key参数，然后取决于函数调用的速度）
• 使用Python可以使手动循环更快，性能超过两个单独调用min()和max()。

如果输入是非序列可迭代对象：

• min()和max()不能在同一个可迭代对象上使用
  • 需要将可迭代对象转换为list()或tuple()（或者可以使用itertools.tee()，但是根据其文档，在这种情况下list()/tuple()转换更快），但具有较大的内存占用
  • 可以使用单个循环方法，该方法可以再次通过Cython加速。

这里没有详细讨论显式key的情况，但下面报告了一种可以进行Cython适应的高效方法之一：

def extrema_for_with_key(items, key=None):
    items = iter(items)
    if callable(key):
        try:
            max_item = min_item = next(items)
            max_val = min_val = key(item)
        except StopIteration:
            return None, None
        else:
            for item in items:
                val = key(item)
                if val > max_val:
                    max_val = val
                    max_item = item
                elif val < min_val:
                    min_val = val
                    min_item = item
            return max_item, min_item
    else:
        try:
            max_item = min_item = next(items)
        except StopIteration:
            return None, None
        else:
            for item in items:
                if item > max_item:
                    max_item = item
                elif item < min_item:
                    min_item = item
            return max_item, min_item

完整的基准测试在这里。

---

更长的答案

虽然在纯Python中循环可能成为瓶颈，但是寻找最大值和最小值的问题可以用比两次单独调用max()和min()更少的步骤（比较和赋值）来解决——在随机分布的值序列上，更具体地说，只需遍历一次该序列（或可迭代对象）即可。 当使用key参数提供的功能时，或者当输入是一个迭代器并且将其转换为tuple()或list()（或使用itertools.tee()）会导致过多的内存消耗时，这可能是有用的。 此外，如果可以通过Cython或Numba加速循环，则这种方法可能会导致更快的执行。 如果输入不是NumPy数组，则Cython的加速效果最佳，而如果输入是NumPy数组，则Numba的加速效果最大。 通常，将通用输入转换为NumPy数组的成本不会抵消使用Numba的速度增益。 有关NumPy数组的情况的讨论可以在此处找到。

基本实现，忽略`key`参数，如下（其中`min_loops()`和`max_loops()`本质上是使用循环重新实现的`min()`和`max()`）：

def min_loops(seq):
    iseq = iter(seq)  # ensure iterator
    try:
        result = next(iseq)
    except StopIteration:
        return None
    else:
        for item in iseq:
            if item < result:
                result = item
        return result


def max_loops(seq):
    iseq = iter(seq)  # ensure iterator
    try:
        result = next(iseq)
    except StopIteration:
        return None
    else:
        for item in iseq:
            if item > result:
                result = item
        return result


def extrema_loops(items):
    seq = tuple(items)  # required if items is actually an iterable
    return max_loops(seq), min_loops(seq)

这些可以天真地组合成一个单循环，类似于 OP 的建议：

def extrema_for(seq):
    iseq = iter(seq)
    try:
        max_val = min_val = next(iseq)
    except StopIteration:
        return None, None
    else:
        for item in iseq:
            if item > max_val:
                max_val = item
            elif item < min_val:  # <-- reduces comparisons
                min_val = item
        return max_val, min_val

“elif”的使用可以有效地减少比较和赋值的数量（对于具有随机分布值的输入，“平均”每个元素约为1.5次）。通过同时考虑两个元素（在这两种情况下，“平均”每个元素的比较次数都为1.5），可以进一步减少赋值的数量。”

def extrema_for2(seq):
    iseq = iter(seq)
    try:
        max_val = min_val = next(iseq)
    except StopIteration:
        return None, None
    else:
        for x, y in zip(iseq, iseq):
            if x > y:  # reduces assignments
                x, y = y, x
            if x < min_val:
                min_val = x
            if y > max_val:
                max_val = y
        try:
            last = next(iseq)
        except StopIteration:
            pass
        else:
            if last < min_val:
                min_val = x
            if last > max_val:
                max_val = y
        return max_val, min_val

每种方法的相对速度在很大程度上取决于每个指令的相对速度，而extrema_for2（）的替代实现可能会更快。例如，如果将主循环（for x，y in zip（iseq，iseq））替换为while True：x = next（iseq）; y = next（iseq）结构，即：

def extrema_while(seq):
    iseq = iter(seq)
    try:
        max_val = min_val = x = next(iseq)
        try:
            while True:
                x = next(iseq)
                y = next(iseq)
                if x > y:
                    x, y = y, x
                if x < min_val:
                    min_val = x
                if y > max_val:
                    max_val = y
        except StopIteration:
            if x < min_val:
                min_val = x
            if x > max_val:
                max_val = x
            return max_val, min_val
    except StopIteration:
        return None, None

这在Python中实现起来较慢，但是使用Cython加速后会更快。

这些以及以下的实现作为基准：

def extrema(seq):
    return max(seq), min(seq)

def extrema_iter(items):
    seq = tuple(items)
    return max(seq), min(seq)

下面进行比较：

请注意一般情况下：

• extrema_while() > extrema_loops() > extrema_for() > extrema_for2()（这是由于对next()的昂贵调用）
• extrema_loops_cy() > extrema_for_cy() > extrema_for2_cy() > extrema_while_cy()
• extrema_loops_cy()实际上比extrema()更慢。

函数有Cython对应项（带有_cy后缀），除了使用cpdef替换def外，本质上是相同的代码，例如：

%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True

cpdef extrema_while_cy(seq):
    items = iter(seq)
    try:
        max_val = min_val = x = next(items)
        try:
            while True:
                x = next(items)
                y = next(items)
                if x > y:
                    x, y = y, x
                if x < min_val:
                    min_val = x
                if y > max_val:
                    max_val = y
        except StopIteration:
            if x < min_val:
                min_val = x
            if x > max_val:
                max_val = x
            return max_val, min_val
    except StopIteration:
        return None, None

完整基准测试在此处。

- norok2

---

不错，@norok2。 - OTheDev

昨晚我写了一个带有minmax实现的C扩展模块。不过我还需要进行微调和测试。我很好奇为什么还没有实现一个内置的minmax。 - OTheDev

Answer 3

请查看这里：

这不完全是您要找的，但我可以减少循环：

def min_max(iterable):
    if not iterable:
        raise Exception('Required iterable object')
    _min = _max = iterable[0]
    ind = 0
    if len(iterable) & 1:
        ind = 1
    for elm in iterable[1::2]:
        ind += 2
        try:
            if iterable[ind] < iterable[ind + 1]:
                if _min > iterable[ind]:
                    _min = iterable[ind]
                if _max < iterable[ind + 1]:
                    _max = iterable[ind + 1]
            else:
                if _min > iterable[ind + 1]:
                    _min = iterable[ind + 1]
                if _max < iterable[ind]:
                    _max = iterable[ind]
        except:
            pass
    return _min, _max

print min_max([11,2,3,5,0,1000,14,5,100,1,999])

输出：

(0, 1000)

- James Sapam

---

-1；这并没有回答问题。而且我也不确定你在那里做什么... - poke

好的，我提供了一个更好的解决方案，如果所有者不喜欢，我会将其删除。我正在将循环次数减少到n/2。 - James Sapam

如果@user3398620不喜欢，请告诉我 :) 我会将其删除。 - James Sapam

好的，我总是可以进行循环展开来消除迭代;但这并不会改变复杂度(我认为这使得您的函数更加复杂)。此外，您的解决方案不支持关键函数，并且基于序列而不是可迭代对象（比OP更甚）。 - poke

Answer 4

请使用以下代码：

for i in iterable[1:]:
    if key(i) > key(max_): 
        max_ = i
    elif key(i) < key(min_):
        min_ = i

- BlackMamba