python - 如何在python中获取列表的最小和最大元素

Question

如果有一个像这样的列表:

l = [1,2,3,4,5]

我想在最后

min = 1   
max = 5

没有 min(l) 和 max(l)。

Answer 1

如果您试图避免使用两个循环，希望单个循环会更快，则需要重新考虑。调用两个 O(N) 函数仍然会为您提供一个 O(N) 算法，您所做的只是将常量每次迭代成本加倍。带有比较的单个 Python 循环也不能比 O(N) 做得更好(除非您的数据已经排序)，并且为每次迭代解释字节码也有相当大的恒定成本。哪种方法具有更高的固定成本只能通过计算运行时间来确定。

要在单个循环中执行此操作，请遍历列表并根据目前找到的最小值和最大值测试每个项目。 float('inf') 和 float('-inf')(无穷大和负无穷大)是简化逻辑的良好起点:

minimum = float('inf')
maximum = float('-inf')
for item in l:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

或者，从第一个元素开始，只遍历其余元素。首先将列表变成可迭代对象，将第一个元素存储为最新结果，然后循环遍历其余元素:

iterl = iter(l)
minimum = maximum = next(iterl)
for item in iterl:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

不要使用排序。 Python 的 Tim Sort 实现是一个 O(N log N) 算法，预计它会比直接的 O(N) 方法慢。

与更大的随机列表进行时间比较:

>>> from random import shuffle
>>> l = list(range(1000))
>>> shuffle(l)
>>> from timeit import timeit
>>> def straight_min_max(l):
...     return min(l), max(l)
... 
>>> def sorted_min_max(l):
...     s = sorted(l)
...     return s[0], s[-1]
... 
>>> def looping(l):
...     l = iter(l)
...     min = max = next(l)
...     for i in l:
...         if i < min: min = i
...         if i > max: max = i
...     return min, max
... 
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10000)
0.5266690254211426
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10000)
2.162343978881836
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10000)
1.1799919605255127

因此，即使对于包含 1000 个元素的列表，min() 和 max() 函数也是最快的。排序在这里最慢。如果您允许就地排序，排序版本会更快，但是您还需要为每次定时运行生成一个新的随机列表。

移动到一百万个项目(每次定时运行仅 10 个测试)，我们看到:

>>> l = list(range(1000000))
>>> shuffle(l)
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10)
1.6176080703735352
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10)
6.310506105422974
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10)
1.7502741813659668

最后但同样重要的是，使用一百万个项目和 l.sort() 而不是 sorted():

>>> def sort_min_max(l):
...     l.sort()
...     return l[0], l[-1]
... 
>>> timeit('f(l[:])', 'from __main__ import straight_min_max as f, l', number=10)
1.8858389854431152
>>> timeit('f(l[:])', 'from __main__ import sort_min_max as f, l', number=10)
8.408858060836792
>>> timeit('f(l[:])', 'from __main__ import looping as f, l', number=10)
2.003532886505127

注意l[:]；我们给每个测试运行一份列表的副本。

结论:即使对于大型列表，您最好还是使用 min() 和 max() 函数，因为很难击败低迭代次数一个好的 C 循环的成本。但如果您不得不放弃这些功能，直接循环是下一个更好的选择。