我怎样才能获得的最小和列表的蟒蛇

答

我能想到的是排序的原始列表，然后选择第一个和最后一个元素最快的方法。这避免了多次循环，但它确实会破坏列表的原始结构。这可以通过简单地复制列表并仅对复制列表进行排序来解决。我很好奇，如果这是不是仅仅使用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

出人意料的是，第二种方法是通过我的电脑上10ms左右的速度更快。不知道这对非常大的列表会有多大的效果，但这种方法对于您提供的示例列表至少更快。

我在我的计时脚本中添加了@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

排序算法对大型阵列很慢。

+0

您需要使用'timeit'模块来消除方差（CPU调度，交换等）;它也会为您的平台选择正确的计时器（最准确的选项）。 –

+1

而一个简单的循环是O（n）的复杂度，排序是O（n log n）;这可能是因为python for循环的不变成本高于排序的C代码常量成本，这就是为什么排序后短列表可能会更快，但对于大列表循环会赢，给定足够大的名单。 –

+1

最后一个数据点：使用一个正确的随机列表来测试sort（）对一个循环或者min（）和max（）调用;排序算法（TimSort）针对部分排序的数据进行了优化;你的输入样本大多是排序的（只有'3'不在位）。 –

答

如果您试图避免使用两个循环，希望单个循环会更快，您需要重新考虑。调用两个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循环的低每次迭代成本。但是如果你不得不放弃这些功能，直线循环是下一个更好的选择。

+1

你应该更好地给他提示，而不是给他答案，*不是为学生做作业！：-s（尽管你使用float的'inf'的想法很整洁;-)） – zmo

+3

不，Stack Overflow用于回答问题。 OP从来没有要求提示，我们不是在这里警察的作业政策。如果我是教授，如果将其作为家庭作业答案发布，以了解学生是否了解其确切* *，我*会在答案中询问有关代码的尖锐问题。 –

+2

在这种情况下，我会使用'iterable = iter（l）; minimum = maximum = next（iterable）'“pattern”。它具有额外的优点，即它可以处理每个序列，而'l [0]'仅适用于索引序列。 – Bakuriu

答

使用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

+4

为什么双循环？你可以在这里避免循环两次。 –

+0

的确如此，但我认为从教育的角度来看更清楚。 – DXsmiley

+3

@DXsmiley我不同意 – jamylak

答

好吧，因为这是一项任务，我不会给你任何代码，你必须自己弄明白。但基本上，您可以在列表中循环，例如创建两个变量iMin和iMax，并将每个值与iMin和iMax对比，然后将新变量iBuf分配给该值。

+0

这些名称似乎太过java-ish或任何语言使用camelCase + prepending类型，我认为这是完全丑陋和误导在这个示例中（其中函数将支持任何类型的支持比较）。 – Bakuriu

+0

我说的是一般算法，不是具体的python，我用'i'来表示'index'，而不是'整数'。我不喜欢python中的camelCase，顺便说一句。 – zmo

答

怪异限制家庭作业问题，要求回答作弊

>>> l = [1,2,3,4,5] 
>>> sorted(l)[::len(l)-1] 
[1, 5]

答

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

答

如果你只需要一个通过列表循环，您可以使用一个reduce（不那么）创造性的方式。助手功能可能已经降低拉姆达，但我不这样做是为了便于阅读的缘故

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

答

为了找到最大：

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()))

我怎样才能获得的最小和列表的蟒蛇

相关推荐