maximum() efficency

[Paul McGuire]

"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