最大（）效率 [英] maximum() efficency
问题描述
我正在查看Python函数以从列表中找到最大值。
原始版本更复杂;我简化了它。内置的max（）
函数可以替换简化的示例，但不能替换原始的。
def maximum（lst）：
maxval = lst [0]
$ x $ b for x in xrange（1，len（lst））：
v = lst [i]
如果maxval> v：
maxval = v
返回maxval
我立即开始考虑如何提高效率。我的
首先想到的是使用迭代器：
def最大值（lst）：
itr = iter（lst）
maxval = itr.next（）
for v in itr：
if maxval> v：
maxval = v
返回maxval
然后我想，我想知道是否有更快的速度解决方案，*不使用
迭代器，用于旧版本的Python。我想出了：
def最大值（lst）：
a = []
for v in lst：
尝试：
如果a [0]> v：
a [0] = v
除了IndexError：
a.append（v）
返回a [0]
当然，使用[0]而不是maxval来说有点难看。而且我是试图不对列表编制索引，而在这里我正在索引另一个列表。所以：
def最大值（lst）：
for v in lst：
试试：
if maxval> ; v：
maxval = v
除了NameError：
maxval = v
return maxval
我们最后得到的是我的实际问题：这可以保证在所有版本的Python上工作吗？
在我的在我的电脑上测试，上面的功能完美无缺。即使
如果你这样做：
maxval = 100
打印最大值（cmp，[2,0,3,1]）
3
换句话说，即使有一个带有该名称的
全局变量，你也会在函数中得到一个NameError。这是用Python 2.4，然而......是
这个函数保证在所有Python版本中都能运行吗？我很满意a [0]版本，因为我明确地设置了一个空的
列表，我知道[0]总会引发该IndexError。
PS我继续对上面的函数进行基准测试，再加上一个类似于[0]解决方案的b $ b，但是使用了一个空字典而不是一个零长度列表的
。我创建了一个百万个零的列表，然后
在列表的开头存储了1。因此，最大的函数将花费所有时间来迭代值并比较它们，并且非常好地更新maxval或其等价物。每次运行每个功能的时间
在大清单上100次：
36.8秒xrange
22.3秒迭代器
39.2秒一个[0]上的IndexError
31.5秒带有maxval的NameError
43.4秒空字典上的KeyError
结论我从这些数字中得出：
有例外的偷偷摸摸的技巧没有带来足够的速度值得使用; b $ b使用;其中两个实际上比xrange解决方案慢。甚至
NameError只有一点点快，而且简单比
复杂，所以我不认为我实际上会使用它。
明显的赢家是迭代器版本。它比
其他人要快得多，而且在我看来，它比其他人的b / b
更简单易懂。
- -
Steve R. HastingsVita est
st *** @ hastings.org http://www.blarg.net/~steveha
Steve R. Hastings写道：我正在查看Python函数以从列表中找到最大值。
原件更复杂;我简化了它。内置的max（）
函数可以替换简化的示例，但不能替换原始函数。
原始版本是什么？你确定max不能用一个
适当的decorate-sort-undecorate（DSU）或者来自Python 2.5的key =参数
来解决它？
STeVe
Steve R. Hastings写道：我正在寻找一个Python函数来找到最大值从列表中。
原件更复杂;我简化了它。内置的max（）
函数可以替换简化的示例，但不能替换原始函数。
但是你忘了给我们原来的东西......
[剪几个实现]
当然，使用[0]而不是maxval来说有点难看。而且我在尝试不对列表编制索引，而在这里我正在索引另一个列表。所以：
def最大值（lst）：
for v in lst：
试试：
if maxval> v：
maxval = v
除了NameError：
maxval = v
返回maxval
在我的电脑测试中，上述功能完美无缺。即使
如果你这样做：
maxval = 100
打印最大值（cmp，[2,0,3,1] ]）3
换句话说，即使有一个带有该名称的全局变量，你也会在函数中得到一个NameError。那就是Python 2.4，但是......
这个函数保证可以在所有Python版本中使用吗？
不是100％肯定，但我想是的。拥有较长python经验的人肯定会回答
。或者你可以自己尝试一下。
它起作用的原因是：
def f（）：
打印一个
a = 7; f（）
工作和打印7（使用全局a），而这个
def f（）：
打印
a = 12
a = 7; f（）
不起作用。 Python注意到a将被分配到f内部并将其视为局部变量
。您的代码也是如此。试试上面的例子，不用
a = 7并注意不同的错误信息...
明显的赢家是迭代器版本。它比其他人快得多，而且在我看来，它比其他人更容易理解。
我会以同样的方式完成它，但可能没有迭代器。即，像这样：
def最大值（lst）：
尝试：m = lst [0]
除外（TypeError） ，IndexError）：引发异常给予
最大值的非序列或空序列）
＃（您忘记了代码中的上述完整性检查。
＃不是绝对必要的，但很高兴。）
for x in lst：
如果x> m： m = x
返回m
" Steve R. Hastings" < ST *** @ hastings.org>在消息中写道
news：pa **************************** @ hastings.org .. < blockquote class =post_quotes>我正在查看Python函数以从列表中找到最大值。
原始版本更复杂;我简化了它。内置的max（）
函数可以替换简化的示例，但不能替换原始函数。
如果您对最小值和最大值都感兴趣，这是一个算法
，每2个列表项只执行3次比较，而不是
暴力方法的4次比较。这将成对地输入输入列表，
将这两个项目相互比较，然后将较小的值与当前最小值的
进行比较，将当前最大值与较大值进行比较。 />
def minMax（L）：
lenL = len（L）
如果lenL == 0：
返回无，无
如果lenL == 1：
返回L [0]，L [0]
min_ = max_ = L [0]
if lenL％2：
i = 1
else：
i = 0
而i< lenL：
a，b = L [i]，L [i + 1]
如果a> b：
a，b = b，a
如果a< min_：min_ = a
如果b> max_：max_ = b
i + = 2
返回min_，max_
当然，这很多Python字节码并不像简单地调用内置的min（）和max（）那样快。但是，如果你在混合物中添加psyco，那么物质就不会那么干净了。我使用
随机生成的字符串列表测试了这个方法，在列表长度超过100-500左右后，
minMax开始超过编译的min（）和max（）。下面的
表显示了暴力min（）和max（）调用的时间，接着是minMax（）的
：
列表长度1：0.0000229 0.0000612
列表长度2：0.0000056 0.0001081
列表长度10：0.0000059 0.0000707
列表长度100：0.0000154 0.0000087
列表长度500：0.0000589 0.0000534
列表长度1000：0.0001176 0.0000670
列表长度10000：0.0011485 0.0008954
列表长度100000：0.0126720 0.0077379
使用OP'的100万个零的测试，第一个零变为1，
这里是minMax与min（）和max（）的性能：
列表长度1000000：0.1235953 0.0126896
minMax快10倍！具有讽刺意味的是，调用minMax（）比调用
min（）或max（）更快。
如果你的列表包含昂贵的对象比较，交叉
列表长度可能会短得多。
- Paul
I was looking at a Python function to find the maximum from a list.
The original was more complicated; I simplified it. The built-in max()
function can replace the simplified example, but not the original.
def maximum(lst):
maxval = lst[0]
for i in xrange(1, len(lst)):
v = lst[i]
if maxval > v:
maxval = v
return maxval
Immediately I started thinking about ways to make this more efficient. My
first thought was to use iterators:
def maximum(lst):
itr = iter(lst)
maxval = itr.next()
for v in itr:
if maxval > v:
maxval = v
return maxval
Then I thought, I wonder if there is a faster solution that *doesn''t* use
iterators, for use with older versions of Python. I came up with:
def maximum(lst):
a = []
for v in lst:
try:
if a[0] > v:
a[0] = v
except IndexError:
a.append(v)
return a[0]
Of course, it''s a little ugly to use a[0] instead of "maxval". And I''m
trying not to index a list, and here I am indexing another list. So:
def maximum(lst):
for v in lst:
try:
if maxval > v:
maxval = v
except NameError:
maxval = v
return maxval
And we come at last to my actual question: Is this guaranteed to work on
all versions of Python?
In my testing on my computer, the above function works perfectly. Even
if you do this:
maxval = 100
print maximum(cmp, [2, 0, 3, 1])
3
In other words, you get a NameError in the function even if there is a
global variable with that name. That''s with Python 2.4, however... is
this function guaranteed to work in all Python versions? I am very
comfortable with the a[0] version, since I explicitly set a to an empty
list, I know a[0] will always raise that IndexError.
P.S. I went ahead and benchmarked the above functions, plus one more
that is similar to the a[0] solution but used an empty dictionary instead
of a zero-length list. I created a list of a million zeroes, and then
stored a 1 at the beginning of the list. Thus the maximum functions would
spend all their time iterating through values and comparing them, and very
little time updating maxval or its equivalent. Times to run each function
100 times on the large list:
36.8 seconds xrange
22.3 seconds iterator
39.2 seconds IndexError on a[0]
31.5 seconds NameError with maxval
43.4 seconds KeyError on empty dictionary
The conclusions I draw from these numbers:
The sneaky tricks with exceptions don''t bring enough speed to be worth
using; two of them were actually slower than the xrange solution. Even
the NameError one was only a little bit faster, and simple is better than
complex, so I don''t think I''d ever actually use it.
The clear winner was the iterator version. It was much faster than the
others, and in my opinion it is simpler and easier to understand than any
of the others.
--
Steve R. Hastings "Vita est"
st***@hastings.org http://www.blarg.net/~steveha
Steve R. Hastings wrote:I was looking at a Python function to find the maximum from a list.
The original was more complicated; I simplified it. The built-in max()
function can replace the simplified example, but not the original.
What''s the original? Are you sure max can''t solve it with an
appropriate decorate-sort-undecorate (DSU) or the key= argument coming
in Python 2.5?
STeVe
Steve R. Hastings wrote:I was looking at a Python function to find the maximum from a list.
The original was more complicated; I simplified it. The built-in max()
function can replace the simplified example, but not the original.
But you forgot to shuw us the original...
[snip several implementations]
Of course, it''s a little ugly to use a[0] instead of "maxval". And I''m
trying not to index a list, and here I am indexing another list. So:
def maximum(lst):
for v in lst:
try:
if maxval > v:
maxval = v
except NameError:
maxval = v
return maxval
In my testing on my computer, the above function works perfectly. Even
if you do this:maxval = 100
print maximum(cmp, [2, 0, 3, 1])3
In other words, you get a NameError in the function even if there is a
global variable with that name. That''s with Python 2.4, however... is
this function guaranteed to work in all Python versions?
Not 100% sure, but I think yes. People with longer experience in python can answer
definitely. Or you can try it out yourself.
The reason it works is that this:
def f():
print a
a=7; f()
works and prints 7 (global a is used), while this
def f():
print a
a = 12
a=7; f()
does NOT work. Python notices that a is going to get assigned to inside f and treats it as
a local variable. This is also the case with your code. Try out the above examples without
a=7 and notice the different error messages...
The clear winner was the iterator version. It was much faster than the
others, and in my opinion it is simpler and easier to understand than any
of the others.
I would have done it in the same way, but probably without the iterators. I.e., like this:
def maximum(lst):
try: m = lst[0]
except (TypeError, IndexError): raise Exception "Non-sequence or empty sequence given to
maximum")
# (you forgot the above sanity checks in your code.
# not strictly necessary, but nice to have.)
for x in lst:
if x>m: m=x
return m
"Steve R. Hastings" <st***@hastings.org> wrote in message
news:pa****************************@hastings.org.. .I was looking at a Python function to find the maximum from a list.
The original was more complicated; I simplified it. The built-in max()
function can replace the simplified example, but not the original.
If you are interested in both the min and max values, here is an algorithm
that performs only 3 comparisons for every 2 list items, instead of the
brute force method''s 4 comparisons. This walks the input list in pairs,
compares the two items to each other, then compares the lesser with the
current min and the greater with the current max.
def minMax(L):
lenL = len(L)
if lenL == 0:
return None,None
if lenL == 1:
return L[0],L[0]
min_ = max_ = L[0]
if lenL % 2:
i = 1
else:
i = 0
while i < lenL:
a,b = L[i],L[i+1]
if a > b:
a,b = b,a
if a < min_: min_ = a
if b > max_: max_ = b
i += 2
return min_,max_
Of course, this much Python bytecode is not near as fast as simply calling
the builtins min() and max(). But, if you add psyco to the mix, things
aren''t so cut-and-dried. I tested this method using a list of
randomly-generated strings, and after the list length exceeds 100-500 or so,
minMax starts to outperform the compiled min() and max(). The following
table shows the timing for the brute force min() and max() calls, followed
by minMax():
List length 1: 0.0000229 0.0000612
List length 2: 0.0000056 0.0001081
List length 10: 0.0000059 0.0000707
List length 100: 0.0000154 0.0000087
List length 500: 0.0000589 0.0000534
List length 1000: 0.0001176 0.0000670
List length 10000: 0.0011485 0.0008954
List length 100000: 0.0126720 0.0077379
Using the OP''s test of 1 million zeros with the first zero changed to a 1,
here is the performance of minMax vs. min() and max():
List length 1000000: 0.1235953 0.0126896
minMax is 10X faster! Ironically, it''s faster calling minMax() than either
min() or max().
If your list contains objects that are expensive to compare, the crossover
list length may be much shorter.
-- Paul
这篇关于最大（）效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
