从列表中获取最小值和最大值的高效方法？

Question

我的问题来源于回答如何在Python 3中找到任意列表中的缺失数字？。

大多数解决方案建议使用类似于

a = [10,12,13,8]
# get set of full numbers
allNums = set( (x for x in range(min(a),max(a)+1)))
# do some kind of set operation / symetric difference 

这需要2次迭代a来获取列表中的min(a)和max(a)作为值，以构建包括min(a)和max(a)之间所有数字的范围。

很容易将其简化为只需一次a的操作：

def minmax(data):
    """Get the min and max of an iterable in O(n) time and constant space."""
    minValue = data[0]
    maxValue = data[0]
    for d in data[1:]:
        minValue = d if d < minValue else minValue
        maxValue = d if d > maxValue else maxValue
    return (minValue,maxValue)

有没有一种使用Python内置/模块的方法以O(n)时间和常量空间检索？

编辑： 同意：min()和max()也都是O(n) - 但使用两次（这是常数并减少到O(n) - 是的）- 但两次比一次慢。

---

带有一些基准测试的编辑：

import timeit

# 100k random numbers to min/max upon
data = """import random
random.seed(42)
data = random.choices(range(1000000),k=100000)"""

Functool reduce approach:

t1 = timeit.timeit("""
mi,ma=minmax(data)
""",setup="""
import functools

def minmax(aa):
    return functools.reduce(lambda mm,xx : ( min(mm[0],xx),max(mm[1],xx)) , aa, ( aa[0],aa[0],))
""" + data, number = 1000 )

简单的最小值和最大值用法：

t2 = timeit.timeit("""
mi,ma=min(data),max(data)
""",setup=data, number = 1000)

使用if/elif一次尝试来减少比较：

t3 = timeit.timeit("""
mi,ma=minmax(data) 
""",setup="""
def minmax(data):
    minValue = data[0]
    maxValue = data[0]
    for d in data[1:]:
        if d < minValue:     # changed to if / elif: in a vain attempt to make it faster
            minValue = d     # its closer to the proposed solution in the numpy-question 
        elif d > maxValue:   # linked above
            maxValue = d
    return (minValue,maxValue)
""" + data, number = 1000)

不使用 if/elif 的一次尝试（需要更多比较）：

t4 = timeit.timeit("""
mi,ma=minmax(data) 
""",setup="""
def minmax(data):
    minValue = data[0]
    maxValue = data[0]
    for d in data[1:]:
        minValue = d if d < minValue else minValue 
        maxValue = d if d > maxValue else maxValue 
    return (minValue,maxValue)
""" + data, number = 1000)

这导致：

minmanx-reduce:      148.5929143627707   
default min + max:     3.376458476185718     # ouch .. seems we just use these
minmax1passOptimized: 15.975109436292087   
minmax1pass:          20.29275910515082

- Patrick Artner

---

O(n + n) = O(n) 的意思是，对于一个算法的时间复杂度为线性的情况下，在计算过程中出现的常数项可以忽略不计。因此，将两个n相加并不会改变算法的渐进时间复杂度，仍然为O(n)。 - taras

请使用 min(list) 和 max(list)。 - bigbounty

@PatrickArtner，这取决于您的算法复杂性和需要查找最小值和最大值的次数。我很难想象出这2n种情况成为瓶颈的问题。 - taras

@PatrickArtner，你可能会发现对于这个类似问题的答案很有趣。 - taras

首先，你提出的两种解决方案都需要2n次比较（O(n)渐近）。如果你想要一个更好的方法，你可以在少于2n次比较中找到最小值和最大值，实际上你可以在1.5n次比较中找到它们，例如见这里：http://www.cs.nthu.edu.tw/~wkhon/algo09/lectures/lecture8.pdf。当然，从渐近意义上讲，两种方法都是O(n)，但是在实际情况中，1.5n次比较比2n次比较更快。 - coder

Answer 1

你可以使用 functools.reduce。

import functools

def minmax(aa):
    return functools.reduce(lambda mm,xx : ( min(mm[0],xx),max(mm[1],xx)) , aa, ( aa[0],aa[0],))

print(minmax([10,25,5,100,12,32])) # print (5, 100)

- napuzba

---

我认为你应该把这个时间与只调用一次 min 和 max 进行比较。 - timgeb

这种方法速度较慢，但可以回答问题。 - napuzba