What is the maximum Python chooses with a tie?

Question

When using the max() function in Python to find the maximum value in a list (or tuple, dict, etc.) And is there a binding to the maximum value, which one does Python choose? Is this a coincidence?

This is true if, for example, one has a list of tuples and the other selects a maximum (using key= ) based on the first element of the tuple, but there are other second elements. How does Python decide which one to choose as maximum?

Answer 1

He selects the first element that he sees. See the documentation for max() :

If several elements are maximal, the function returns the first element encountered. This is consistent with other sorting stability tools, such as sorted(iterable, key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc) .

In the source code, this is implemented in ./Python/bltinmodule.c using builtin_max , which wraps the more general min_max function .

min_max will min_max over the values ​​and use PyObject_RichCompareBool to see if they are greater than the current value. If so, a larger value replaces it. Equal values ​​will be skipped.

As a result, the first maximum will be chosen in the event of a tie.

Answer 2

From empirical testing, it seems that max() and min() in the list will return the first in the list, which corresponds to max() / min() in case of equality:

 >>> test = [(1, "a"), (1, "b"), (2, "c"), (2, "d")] >>> max(test, key=lambda x: x[0]) (2, 'c') >>> test = [(1, "a"), (1, "b"), (2, "d"), (2, "c")] >>> max(test, key=lambda x: x[0]) (2, 'd') >>> min(test, key=lambda x: x[0]) (1, 'a') >>> test = [(1, "b"), (1, "a"), (2, "d"), (2, "c")] >>> min(test, key=lambda x: x[0]) (1, 'b') 

And Jeremy is perfectly watching that this is true.

Answer 3

For Python 3, the behavior of max() in the case of relationships is no longer just an implementation detail, as described in other answers in detail. This feature is now guaranteed, as the Python 3 documentation explicitly states:

If multiple elements are maximal, the function returns the first one encountered. This is consistent with other sorting stability tools, such as sorted(iterable, key=keyfunc, reverse=True)[0] and heapq.nlargest(1, iterable, key=keyfunc) .

Answer 4

Your question leads to a note a little. when sorting a data structure, there is often a desire to maintain the relative order of objects that are considered equal for comparison purposes. This will be known as stable sorting .

If you absolutely need this function, you can make sort() that is stable , and then know the order relative to the original list.

As for the python itself, I do not believe that you will get any guarantee of which element you will get when you call max() . Other answers give cpython's answer, but other implementations (IronPython, Jython) may work differently.

Answer 5

For versions of Python 2, IMO, I suppose you cannot assume that max() returns the first maximum element in the list in the case of links. I have this belief, because max() supposed to implement the true mathematical function max , which is used in sets that have full order and where the elements have no "hidden information".

(I assume that others explored correctly, and the Python documentation provides no guarantees for max() .)

(In general, there are an infinite number of questions that you can ask about the behavior of a library function, and almost all of them cannot be answered. For example: How much max() stack space will it use? Does it use SSE? How much temporary memory? Can it compare the same pair of objects more than once (if the comparison has a side effect)? Can it work faster than O (n) time for "special" known data structures ?.)