同时获取最小值和最大值的函数速度是否优于单独使用最小值和最大值？

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_

但我在想，既然在循环里我反正要进行两次比较，那直接分别用 min 和 max 不是更快吗？如果是这样的话，我该怎么修改这个函数，让它更高效呢？

Answer 1

使用这段代码：

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

Answer 2

请查看这里：

这可能不是你想要的，但我可以简化这个循环：

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)

Answer 3

简要说明

如果输入是一个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)

这些可以简单地结合成一个循环，类似于提问者的建议：

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），基本上是相同的代码，只是def替换为cpdef，例如：

%%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

完整基准测试在这里。

Answer 4

在找出列表中的最小值或最大值时，最耗时的部分并不是比较数值。比较数值其实很快，不会造成问题。真正影响运行时间的是循环。

当你使用 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 函数。确实，实际的键函数才是让 Python 实现变得耗时的原因。这也很有道理。即使是简单的身份函数，你仍然会有函数调用的开销；len(iterable) 需要很多函数调用（用我上面优化的版本）。而函数调用是相当耗时的。

在我的测试中，去掉对键函数的支持后，出现了 实际预期 的结果：遍历一次比遍历两次要快。但对于不是非常大的可迭代对象，差别真的很小。所以，除非遍历可迭代对象非常耗时（不过你可以使用 tee 仍然遍历两次），或者你本来就想遍历它（在这种情况下你可以将其与最小/最大检查结合使用），那么单独使用内置的 max() 和 min() 函数会更快，也更容易使用。而且，它们都有内部优化，如果你没有指定键函数，它们会跳过键函数的调用。

最后，你如何将键函数优化添加到你的代码中呢？不幸的是，只有一种方法可以做到这一点，那就是复制代码。你基本上需要检查是否指定了键函数，如果没有，就跳过函数调用。所以，像这样：

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