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

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

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

Я работаю в Python П2.6.

5 62
python max

5 ответов:

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

в исходном коде CPython 2.7 это реализовано в ./Python/bltinmodule.c by builtin_max[источник], который обертывает более общий min_max функции [источник].

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

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

66

из эмпирического тестирования следует, что 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')

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

20

для Python 3, поведение max() в случае связей это уже не просто деталь реализации, как подробно описано в других ответах. Функция теперь гарантирована, как Python 3 docs явно указано:

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

12

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

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

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

6

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

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

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

2