Quel est le maximum choisi par Python en cas d'égalité?

Question

Lorsque vous utilisez la fonction max() dans Python pour rechercher la valeur maximale dans une liste (ou tuple, dict, etc.) et qu'il existe une égalité pour la valeur maximale, laquelle choisit Python? Est-ce aléatoire?

Ceci est pertinent si, par exemple, on a une liste de tuples et on sélectionne un maximum (en utilisant un key= ) basé sur le premier élément du tuple mais il existe différents seconds éléments. Comment Python choisit-il lequel choisir au maximum?

Je travaille dans Python v2.6.

Answer 1

Ce n'est pas spécifiée dans la documentation et n'est pas dans le portable en Python section de la bibliothèque standard, de sorte que ce comportement peut varier entre les implémentations.

Dans la source de Disponible 2.7 ceci est mis en œuvre en ./Python/bltinmodule.c par builtin_max ^[source], qui enveloppe la plus générale min_max fonction ^[source].

min_max permettra de faire une itération sur les valeurs et de les utiliser PyObject_RichCompareBool ^[docs] pour voir si elles sont supérieures à la valeur actuelle. Si oui, la plus grande valeur, elle remplace. L'égalité des valeurs sera ignorée.

Le résultat est que le premier maximum sera retenue dans le cas d'une cravate.

Answer 2

D'après des tests empiriques, il apparaît que max() et min() sur une liste renverront le premier de la liste qui correspond aux max() / min() en cas d'égalité:

 >>> 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')
 

Et l'excellent travail de Jeremy confirme que c'est bien le cas.

Answer 3

Votre question un peu conduit à une note. Lors du tri d'une structure de données, il est souvent un désir de maintenir un ordre relatif des objets qui sont considérés comme équivalents à des fins de comparaison. Ce qui allait être connu comme un tri stable.

Si vous avez absolument besoin de cette fonctionnalité, vous pourriez faire un sort(), qui sera stable et ensuite avoir connaissance de l'ordre par rapport à la liste initiale.

Comme par python lui-même, je ne crois pas que vous obtenez la garantie de l'élément que vous obtenez lorsque vous appelez max(). D'autres réponses sont à donner le disponible de réponse, mais d'autres implémentations (IronPython, Jython) pourrait fonctionner différemment.

Answer 4

IMO, je crois que vous ne peut pas supposer qu' max() renvoie le premier maximale de l'élément dans la liste dans le cas de liens. J'ai cette conviction parce qu' max() est censé mettre en œuvre la véritable fonction mathématique max, qui est utilisé sur des jeux qui ont un total de la commande, et où les éléments n'ont pas toutes les "informations cachées".

(Je vais supposer que d'autres ont fait des recherches correctement, et le Python de la documentation ne donne pas toutes les garanties pour max().)

(En général, il y a un nombre infini de questions que vous pouvez poser des questions sur le comportement d'une fonction de la bibliothèque, et presque tous ne peuvent pas être répondues. Pour exemple: Combien d'espace de pile sera max() utiliser? Sera-ce l'utilisation de l'ESS? Combien de mémoire temporaire? Peut-il comparer la même paire d'objets, plus d'une fois (si la comparaison a un effet secondaire)? Il peut courir plus vite que O(n) le temps de "spécial" connus des structures de données? etc. etc.)