Какой максимум выбирает Python в случае ничьей?
При использовании max() функция в Python, чтобы найти максимальное значение в списке (или кортеж, dict и т. д.), и есть связь для максимального значения, которое Python выбирает? Это случайно?
Это актуально, если, например, у одного есть список кортежей, а другой выбирает максимум (используя key=) на основе первого элемента кортежа, но существуют разные вторые элементы. Как Python выбирает, какой из них выбрать в качестве максимума?
Я работаю в Python v2.6.
5 ответов
На Python 2 это не указано в документации и отсутствует в разделе переносимых in-Python стандартной библиотеки, поэтому это поведение может отличаться в разных реализациях.
В исходном коде CPython 2.7 это реализовано в ./Python/bltinmodule.c от builtin_max [ источник], который охватывает более общие min_max функция [ источник].
min_max будет перебирать значения и использовать PyObject_RichCompareBool [ документы], чтобы увидеть, если они больше, чем текущее значение. Если это так, большее значение заменяет его. Равные значения будут пропущены.
В результате первый максимум будет выбран в случае ничьей.
Из эмпирических испытаний выясняется, что 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')
И превосходный спор Джереми подтверждает, что это действительно так.
Для Python 3 поведение max() в случае связей это уже не просто детали реализации, как подробно описано в других ответах. Функция теперь гарантирована, так как документы Python 3 явно заявляют:
Если несколько элементов максимальны, функция возвращает первый встреченный элемент. Это согласуется с другими инструментами сохранения стабильности сортировки, такими как sorted(iterable, key=keyfunc, reverse=True)[0] и heapq.nlargest(1, iterable, key=keyfunc).
Ваш вопрос несколько приводит к заметке. При сортировке структуры данных часто возникает желание сохранить относительный порядок объектов, которые считаются равными для целей сравнения. Это будет известно как стабильный вид.
Если вам абсолютно необходима эта функция, вы можете сделать sort(), который будет стабильным, а затем будет знать порядок относительно исходного списка.
Что касается самого питона, я не верю, что вы получаете какую-либо гарантию того, какой элемент вы получите, когда позвоните max(), Другие ответы дают ответ cpython, но другие реализации (IronPython, Jython) могут работать по-другому.
Для версий Python 2, IMO, я полагаю, вы не можете предположить, что max() возвращает первый максимальный элемент в списке в случае связей. У меня есть это убеждение, потому что max() должен реализовать истинную математическую функцию max, который используется на наборах, которые имеют общий порядок, и где элементы не имеют никакой "скрытой информации".
(Я буду предполагать, что другие исследовали правильно, и документация Python не дает никаких гарантий для max() .)
(В общем, вы можете задать бесконечное количество вопросов о поведении библиотечной функции, и почти на все они невозможно ответить. Например: сколько места в стеке будет max() использовать? Будет ли он использовать SSE? Сколько временной памяти? Может ли он сравнивать одну и ту же пару объектов более одного раза (если сравнение имеет побочный эффект)? Может ли он работать быстрее, чем время O(n) для "специальных" известных структур данных? и тд и тп)