Какой максимум выбирает Python в случае ничьей?

Question

При использовании функции max() в Python, чтобы найти максимальное значение в списке (или кортеж, dict и т. Д.), И существует связь для максимального значения, какую из них выбирает Python?Случайно ли это?

Это актуально, если, например, у одного есть список кортежей, а другой выбирает максимум (используя key=) на основе первого элемента кортежа, но есть разные вторые элементы,Как Python выбирает, какой из них выбрать в качестве максимума?

Я работаю в Python v2.6.

Answer 1

В Python 2 это не указано в документации и отсутствует в разделе переносимых in-Python стандартной библиотеки, поэтому это поведение может различаться в разных реализациях.

В исходном коде CPython 2.7 это реализовано в ./Python/bltinmodule.c с помощью builtin_max ^{[ source ]} , который включает в себя более общую функцию min_max ^{[ source ]} .

min_max будет перебирать значения и использовать PyObject_RichCompareBool ^{[ docs ]} , чтобы увидетьесли они больше, чем текущее значение.Если это так, большее значение заменяет его.Равные значения будут пропущены.

В результате будет выбран первый максимум в случае ничьей.

Answer 2

Из эмпирического тестирования выясняется, что max() и min() в списке вернут первое в списке, соответствующее max() / min() в случае связи:

>>> 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')

И Превосходный сон Джереми подтверждает, что это действительно так.

Answer 3

Для Python 3 поведение max() в случае связей больше не является просто деталью реализации, как подробно описано в других ответах.Теперь эта функция гарантирована, поскольку в Python 3 документах явно указано:

Если несколько элементов максимальны, функция возвращает первый встреченный элемент.Это согласуется с другими инструментами сохранения стабильности сортировки, такими как sorted (iterable, key = keyfunc, reverse = True) [0] и heapq.nlargest (1, iterable, key = keyfunc).

Answer 4

Ваш вопрос несколько приводит к заметке. При сортировке структуры данных часто возникает желание сохранить относительный порядок объектов, которые считаются равными для целей сравнения. Это будет известно как стабильная сортировка .

Если вам абсолютно необходима эта функция, вы можете сделать sort(), который будет стабильным , а затем знать порядок относительно исходного списка.

Что касается самого питона, я не верю, что вы получаете какую-либо гарантию того, какой элемент вы получите, когда позвоните max(). Другие ответы дают ответ cpython, но другие реализации (IronPython, Jython) могут работать по-другому.

Answer 5

Для версий Python 2, IMO, я полагаю, вы не можете предположить, что max() возвращает первый максимальный элемент в списке в случае связей. У меня есть такое убеждение, потому что max() должен реализовывать истинную математическую функцию max, которая используется в наборах, имеющих общий порядок, и где элементы не имеют никакой "скрытой информации".

(Я предполагаю, что другие исследовали правильно, и документация Python не дает никаких гарантий для max().)

(В общем, вы можете задать бесконечное количество вопросов о поведении библиотечной функции, и почти на все они невозможно ответить. Например: сколько места в стеке будет max() использовать? Будет ли он использовать SSE? Сколько временной памяти? Может ли он сравнивать одну и ту же пару объектов более одного раза (если сравнение имеет побочный эффект)? Может ли он работать быстрее, чем O (n) время для "специальных" известных структур данных? и т. д.)