[Python-ideas] Make max() stable

[Terry Reedy]

On 1/17/2014 8:45 AM, אלעזר wrote:
> Hi all,
>
> Given several objects with the same key, max() returns the first one:
>
>      >>> key = lambda x: 0
>      >>> max(1, 2, key=key)
>      1

As documented: "If multiple items are maximal, the function returns the 
first one encountered."

> This means it is not stable, at least according to the definition in
> "Elements of Programming" by Alexander Stepanov and Paul McJones (pg. 52):
>
> "Informally, an algorithm is stable if it respects the original order of
> equivalent objects.

Min and max are inherently functions of multisets, with order irrelevant 
but duplicate values allowed. So I do not think 'stability' applies, 
even if a multiset is presented in some arbitrary order.

 > So if we think of minimum and maximum as selecting,
> respectively, the smallest and the second smallest from a list of two
> arguments,

Why not say largest and second largest, but why either rather than just 
smallest and largest?

> stability requires that when called with equivalent elements,
> minimum should return the first and maximum should return the second."

The Python dev who wrote the doc disagrees: "This is consistent with 
other sort-stability preserving tools such as sorted(iterable, 
key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc)."

A simpler reason for the current behavior is that it is more efficient 
to not rebind the internal variable when an equal object is encountered.

In any case, changing the definition and implementation of max will 
break any code that depends on returning first versus last. We have to 
have a good reason to do so. If there is no such code (other than the 
test code that checks the 'first encountered' behavior), then there is 
no need to change.

-- 
Terry Jan Reedy