Które maksimum Python wybiera w przypadku remisu?

Question

Podczas korzystania z funkcji max() w Pythonie, aby znaleźć maksymalną wartość na liście (lub krotkę, dyktowanie itp.) I istnieje remis dla maksymalnej wartości, którą wybiera Python? Czy to jest losowe?

Jest to istotne, jeśli na przykład jedna lista krotek i jedna wybiera maksimum (przy użyciu key=) na podstawie pierwszego elementu krotki, ale istnieją różne drugie elementy. W jaki sposób Python wybiera, który z nich wybrać jako maksimum?

Pracuję w Pythonie v2.6.

Answer 1

W Pythonie 2 nie jest to określone w dokumentacji i nie znajduje się w przenośnej sekcji w Pythonie biblioteki standardowej, więc zachowanie to może się różnić w zależności od implementacji.

W źródle do CPython 2.7 jest realizowana w ./Python/bltinmodule.c przez builtin_max^[source], który owija się bardziej ogólne min_max funkcji ^[source].

min_max będzie iterację wartości i używać PyObject_RichCompareBool^[docs] aby sprawdzić, czy są one większe niż wartość bieżąca. Jeśli tak, to zastępuje ją większa wartość. Wartości równe zostaną pominięte.

Powoduje to, że pierwsze maksimum zostanie wybrane w przypadku remisu.

Answer 2

Z badań empirycznych wynika, że ​​max() i min() na liście powróci pierwsza na liście, który pasuje do max()/min() w przypadku remisu:

>>> 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's excellent sleuthing potwierdza, że ​​jest to w rzeczy samej.

Answer 3

Twoje pytanie w pewnym stopniu prowadzi do notatki. Podczas sortowania struktury danych często zachodzi potrzeba zachowania względnej kolejności obiektów, które są uznawane za równe dla celów porównania. Będzie to znane jako stable sort.

Jeśli absolutnie potrzebujesz tej funkcji, możesz zrobić sort(), którą will be stable, a następnie znać kolejność względem oryginalnej listy.

Jak na samego Pythona, nie wierzę, że masz gwarancję, który element otrzymasz, gdy zadzwonisz pod numer max(). Inne odpowiedzi dają odpowiedź cpython, ale inne implementacje (IronPython, Jython) mogą działać inaczej.

Answer 4

Dla wersji Python 2, IMO, uważam, że nie można założyć, że max() zwraca pierwszy maksymalny element na liście w przypadku więzi. Mam takie przekonanie, ponieważ max() ma zaimplementować prawdziwą funkcję matematyczną max, która jest używana w zestawach, które mają całkowitą kolejność, i gdzie elementy nie mają żadnych "ukrytych informacji".

(Założę się, że inni badali poprawnie, a dokumentacja w Pythonie nie daje żadnych gwarancji na max().)

(Ogólnie, istnieje nieskończona ilość pytań można poprosić o zachowaniu funkcji biblioteki, a prawie wszystkie z nich nie można odpowiedzieć. Na przykład: Ile stos przestrzeń będzie max() wykorzystanie Czy będzie używać SSE? Ile pamięci tymczasowej? Czy może porównać tę samą parę obiektów więcej niż jeden raz (jeśli porównanie ma efekt uboczny)? Czy może działać szybciej niż czas O (n) dla "specjalnych" znanych struktur danych? itp.)

Answer 5

W przypadku Python 3 zachowanie max() w przypadku więzi nie jest już tylko szczegółem implementacji, jak wyszczególniono w innych odpowiedziach. Funkcja jest obecnie zagwarantowane, jako Python 3 docs wyraźnie stwierdzają:

Jeśli wiele rzeczy są maksymalne, funkcja zwraca pierwszy spotkaliśmy. Jest to zgodne z innymi narzędziami do zachowania stabilności sortowania, takimi jak sortowane (iterowalne, key = keyfunc, reverse = True) [0] i heapq.nlargest (1, iterable, key = keyfunc).