Welches Maximum wählt Python bei einem Unentschieden?

Wenn Sie die max()Funktion in Python verwenden, um den Maximalwert in einer Liste zu finden (oder Tupel, Diktat usw.) und es einen Gleichstand für den Maximalwert gibt, welchen wählt Python aus? Ist es zufällig?

Dies ist relevant, wenn man beispielsweise eine Liste von Tupeln hat und ein Maximum (unter Verwendung von a key=) basierend auf dem ersten Element des Tupels auswählt, aber es gibt verschiedene zweite Elemente. Wie entscheidet Python, welches als Maximum ausgewählt wird?

Es wählt das erste Element aus, das es sieht. In der Dokumentation finden Siemax() :

Wenn mehrere Elemente maximal sind, gibt die Funktion das erste gefundene zurück. Dies steht im Einklang mit anderen Werkzeugen zur Erhaltung der Sortierstabilität wie sorted(iterable, key=keyfunc, reverse=True)[0]und heapq.nlargest(1, iterable, key=keyfunc).

Im Quellcode wird dies umgesetzt in ./Python/bltinmodule.cdurchbuiltin_max , die die Wraps allgemeinere min_maxFunktion .

min_maxwird die Werte durchlaufen und verwenden PyObject_RichCompareBool, um festzustellen , ob sie größer als der aktuelle Wert sind. Wenn ja, ersetzt der größere Wert ihn. Gleiche Werte werden übersprungen.

Das Ergebnis ist, dass bei einem Unentschieden das erste Maximum gewählt wird.

Aus empirischen Tests geht hervor, dass max()und min()auf einer Liste die erste in der Liste zurückgegeben wird, die im Falle eines Unentschieden mit dem max()/ übereinstimmt 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')

Und Jeremys exzellente Ermittlungen bestätigen, dass dies tatsächlich der Fall ist.

Für Python 3 ist das Verhalten max()bei Bindungen nicht mehr nur ein Implementierungsdetail, wie in den anderen Antworten beschrieben. Die Funktion ist jetzt garantiert, da in den Python 3-Dokumenten ausdrücklich Folgendes angegeben ist :

Wenn mehrere Elemente maximal sind, gibt die Funktion das erste gefundene zurück. Dies steht im Einklang mit anderen Werkzeugen zur Erhaltung der Sortierstabilität wie sorted(iterable, key=keyfunc, reverse=True)[0]und heapq.nlargest(1, iterable, key=keyfunc).

Ihre Frage führt etwas zu einer Notiz. Beim Sortieren einer Datenstruktur besteht häufig der Wunsch, die relative Reihenfolge von Objekten beizubehalten, die zu Vergleichszwecken als gleich angesehen werden. Dies wäre als stabile Sorte bekannt .

Wenn Sie diese Funktion unbedingt benötigen, können Sie eine ausführen sort(), die stabil ist und dann die Reihenfolge in Bezug auf die ursprüngliche Liste kennt.

Laut Python selbst glaube ich nicht, dass Sie eine Garantie dafür erhalten, welches Element Sie erhalten, wenn Sie anrufen max(). Andere Antworten geben die cpython-Antwort, aber andere Implementierungen (IronPython, Jython) könnten anders funktionieren.

Für Python 2-Versionen, IMO, können Sie meines Erachtens nicht davon ausgehen, dass max()bei Bindungen das erste maximale Element in der Liste zurückgegeben wird. Ich habe diesen Glauben, weil max()er die wahre mathematische Funktion implementieren soll max, die für Mengen verwendet wird, die eine Gesamtreihenfolge haben und bei denen Elemente keine "versteckten Informationen" haben.

(Ich gehe davon aus, dass andere korrekt recherchiert haben und die Python-Dokumentation keine Garantie dafür gibt max().)

(Im Allgemeinen gibt es unendlich viele Fragen, die Sie zum Verhalten einer Bibliotheksfunktion stellen können, und fast alle können nicht beantwortet werden. Beispiel: Wie viel Stapelspeicher wird max()verwendet? Wird SSE verwendet? Wie viel temporärer Speicher? Kann es dasselbe Objektpaar mehr als einmal vergleichen (wenn der Vergleich einen Nebeneffekt hat)? Kann es für "spezielle" bekannte Datenstrukturen schneller als O (n) ausgeführt werden? usw. usw.)