[Python-Dev] [Python-ideas] minmax() function returning (minimum, maximum) tuple of a sequence

[Paul McGuire]

Just as an exercise, I wanted to try my hand at adding a function to the
compiled Python C code.  An interesting optimization that I read about
(where? don't recall) finds the minimum and maximum elements of a sequence
in a single pass, with a 25% reduction in number of comparison operations:
- the sequence elements are read in pairs
- each pair is compared to find smaller/greater
- the smaller is compared to current min
- the greater is compared to current max

So each pair is applied to the running min/max values using 3 comparisons,
vs. 4 that would be required if both were compared to both min and max.

This feels somewhat similar to how divmod returns both quotient and
remainder of a single division operation.

This would be potentially interesting for those cases where min and max are
invoked on the same sequence one after the other, and especially so if the
sequence elements were objects with expensive comparison operations.

However, it *would* add "minmax" to the namespace bloat wherever this
function might land (builtin? itertools? collections?). And I'm sure we
wouldn't want to subsume the current min and max to just be minmax(s)[0] or
minmax(s)[1], since that would *increase* the number of comparisons by 50%
for either function when used alone.

I did my prototyping using Python 2.5.5 source, since I only have Visual
Studio 2005 - here is a diff to the that version's bltinmodule.c file:
http://pastebin.com/4xv6SLBM

Through the magic of Google, I've found these minmax implementations in the
wild:
http://www2-pcmdi.llnl.gov/cdat/source/api-reference/genutil.minmax.html
http://mth.uct.ac.za/~lab/chap1/ans/ans2.pdf

I also found a few other minmax references, but these methods were different
implementations (minimum of sequence of maxima, or a generic min_or_max
function taking a comparison flag or function in order to perform min or
max).  Unfortunately, I did not come up with a good way to search for cases
where min and max were called one after the other.

Any comments? Interest? Should I write up a PEP? Go back to my pyparsing
hole?

-- Paul McGuire