"Steve R. Hastings" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED] > 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 -- http://mail.python.org/mailman/listinfo/python-list