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

Paul McGuire ptmcg at austin.rr.com
Sun Oct 10 20:57:21 CEST 2010

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:

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

More information about the Python-Dev mailing list