maximum() efficency
Paul McGuire
ptmcg at austin.rr._bogus_.com
Sun Mar 26 23:15:56 CEST 2006
"Steve R. Hastings" <steve at hastings.org> wrote in message
news:pan.2006.03.26.17.26.36.252263 at 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
More information about the Python-list
mailing list