[Python-ideas] Make max() stable

Stephen J. Turnbull stephen at xemacs.org
Sat Jan 18 06:26:19 CET 2014


Ned Batchelder writes:
 > On 1/17/14 8:45 AM, אלעזר wrote:

 > > "Informally, an algorithm is stable if it respects the original order 
 > > of equivalent objects. So if we think of minimum and maximum as 
 > > selecting, respectively, the smallest and the second smallest from a 
 > > list of two arguments, stability requires that when called with 
 > > equivalent elements, minimum should return the first and maximum 
 > > should return the second."

 > I don't understand this logic at all. Stability matters in sorting 
 > because sort() takes a sequence and returns a sequence, and for various 
 > reasons you might need to sort a list twice, with different criteria. 
 > Stability guarantees that the second sort won't discard the work of the 
 > first sort.

Two comments.  First, I don't understand at all why earlier members of
a sequence may be presumed to be smaller.  It could easily go the
other way around.

Second, since these operations are *selections* from a collection
(which might impose order or not, which might impose uniqueness or
not), it's the same problem that Steven d'Aprano faced in defining
mode for the statistics PEP: Do you admit failure (here,
noncomparability of some of the maximal 
items), so that a value that
is none of the items must be returned?  In the case of multiple
equivalent values, do you return a representative or the collection?


More information about the Python-ideas mailing list