如果有一个类似的列表：
l = [1,2,3,4,5]
我想在最后
min = 1
max = 5
没有min(l)和max(l)。
问问题
9562 次
8 回答
8
如果您试图避免使用两个循环，希望单个循环会更快，您需要重新考虑。调用两个 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()andmax()函数也是最快的。这里的排序是最慢的。如果您允许就地排序，排序版本可能会更快，但是您还需要为每次定时运行生成一个新的随机列表。
移动到一百万个项目（每次定时运行只有 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()andmax()函数，很难击败良好 C 循环的低每次迭代成本。但是，如果您必须放弃这些功能，那么直接循环是下一个更好的选择。
于 2013-06-05T10:59:47.907 回答
3
寻找最大值：
print reduce(lambda x,y: x if x>y else y, map(int,raw_input().split()))
寻找最小值：
print reduce(lambda x,y: x if x<y else y, map(int,raw_input().split()))
于 2016-10-29T04:20:48.350 回答
1
使用 for 循环遍历列表中的所有元素。将存储最大/最小值的变量设置为列表中的第一个元素以开始。否则，您可能会得到无效值。
max_v=l[0]
for i in l:
if i>max_v:
max_v=i
min_v=l[0]
for i in l:
if l<min_v:
min_v=i
于 2013-06-05T11:00:53.207 回答
1
好吧，因为这是一个作业，我不会给你任何代码，你必须自己弄清楚。但基本上，您遍历列表，创建两个变量iMin，iMax例如，为每个值比较该值iMin并iMax为该值分配一个新变量iBuf。
于 2013-06-05T11:03:05.113 回答
1
具有奇怪限制的家庭作业问题需要作弊答案
>>> l = [1,2,3,4,5]
>>> sorted(l)[::len(l)-1]
[1, 5]
于 2013-06-05T11:13:17.787 回答
0
我能想到的最快方法是对原始列表进行排序，然后选择第一个和最后一个元素。这避免了多次循环，但它确实破坏了列表的原始结构。这可以通过简单地复制列表并仅对复制的列表进行排序来解决。我很好奇这是否比在这个快速示例脚本中使用 max() 和 min() 慢：
import time
l = [1,2,4,5,3]
print "Run 1"
t1 = time.time()
print "Min =", min(l)
print "Max =", max(l)
print "time =", time.time() - t1
print ""
print "l =", l
print ""
l = [1,2,4,5,3]
l1 = list(l)
print "Run 2"
t1 = time.time()
l1.sort()
print "Min =", l1[0]
print "Max =", l1[-1]
print "time =", time.time() - t1
print ""
print "l =", l
print "l1 =", l1
print ""
l = [1,2,4,5,3]
print "Run 3"
minimum = float('inf')
maximum = float('-inf')
for item in l:
if item < minimum:
minimum = item
if item > maximum:
maximum = item
print "Min =", minimum
print "Max =", maximum
print "time =", time.time() - t1
print ""
print "l =", l
令人惊讶的是，第二种方法在我的计算机上快了大约 10 毫秒。不确定这对于非常大的列表有多有效，但至少对于您提供的示例列表，这种方法更快。
我将@Martijn Pieters 的简单循环算法添加到我的计时脚本中。（因为时间是这个问题中唯一值得探讨的重要参数。）我的结果是：
Run 1: 0.0199999809265s
Run 2: 0.00999999046326s
Run 3: 0.0299999713898s
编辑：包含用于计时的 timeit 模块。
import timeit
from random import shuffle
l = range(10000)
shuffle(l)
def Run_1():
#print "Min =", min(l)
#print "Max =", max(l)
return min(l), max(l)
def Run_2():
l1 = list(l)
l1.sort()
#print "Min =", l1[0]
#print "Max =", l1[-1]
return l1[0], l1[-1]
def Run_3():
minimum = float('inf')
maximum = float('-inf')
for item in l:
if item < minimum:
minimum = item
if item > maximum:
maximum = item
#print "Min =", minimum
#print "Max =", maximum
return minimum, maximum
if __name__ == '__main__':
num_runs = 10000
print "Run 1"
run1 = timeit.Timer(Run_1)
time_run1 = run1.repeat(3, num_runs)
print ""
print "Run 2"
run2 = timeit.Timer(Run_2)
time_run2 = run2.repeat(3,num_runs)
print ""
print "Run 3"
run3 = timeit.Timer(Run_3)
time_run3 = run3.repeat(3,num_runs)
print ""
print "Run 1"
for each_time in time_run1:
print "time =", each_time
print ""
print "Run 2"
for each_time in time_run2:
print "time =", each_time
print ""
print "Run 3"
for each_time in time_run3:
print "time =", each_time
print ""
我的结果是：
Run 1
time = 3.42100585452
time = 3.39309908229
time = 3.47903182233
Run 2
time = 26.5261287922
time = 26.2023346397
time = 26.7324208568
Run 3
time = 3.29800945144
time = 3.25067545773
time = 3.29783778232
排序算法对于大型数组非常慢。
于 2013-06-05T11:15:41.663 回答
0
>>> L = [1,2,3,4,5]
>>> reduce(lambda x, y: x if x<y else y, L)
1
>>> reduce(lambda x, y: x if x>y else y, L)
5
另一种方式
>>> it = iter(L)
>>> mn = mx = next(it)
>>> for i in it:
... if i<mn:mn=i
... if i>mx:mx=i
...
>>> mn
1
>>> mx
5
于 2013-06-05T11:27:21.060 回答
0
如果您只需要一个循环遍历列表，则可以使用reduce（不是那么）创造性的方式。辅助函数可以减少为 lambda，但为了便于阅读，我不这样做：
>>> def f(solutions, item):
... return (item if item < solutions[0] else solutions[0],
... item if item > solutions[1] else solutions[1])
...
>>> L = [i for i in range(5)]
>>> functools.reduce(f, L, (L[0],L[0]))
(0, 4)
于 2013-06-05T12:21:10.527 回答