При использовании функции max() в Python, чтобы найти максимальное значение в списке (или кортеж, dict и т.д.) И есть привязка к максимальному значению, какое из них выбирает Python? Это случайно?
Это актуально, если, например, у одного есть список кортежей, а другой выбирает максимум (используя key=) на основе первого элемента кортежа, но есть другие вторые элементы. Как Python решает, какой из них выбрать в качестве максимума?
Он выбирает первый элемент, который видит. Смотрите документацию по max():
Если несколько элементов максимальны, функция возвращает первый встреченный элемент. Это согласуется с другими инструментами сохранения стабильности сортировки, такими как
sorted(iterable, key=keyfunc, reverse=True)[0]иheapq.nlargest(1, iterable, key=keyfunc).
В исходном коде это реализовано в ./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) время для "специальных" известных структур данных?.)