Python在匹配情況下選擇哪個最大值？

Question

當在Python中使用max()函數來查找列表（或元組，字典等）中的最大值時，最大值有一個關係，Python選擇哪一個？它是隨機的嗎？

這是相關的，例如，如果有一個元組列表，並且根據元組的第一個元素選擇最大值（使用key=），但有不同的第二個元素。 Python如何挑選哪一個挑選最大值？

我正在使用Python v2.6。

Answer 1

在Python 2中，這並未在文檔中指定，也不在標準庫的可移植in-Python部分，因此這種行爲在實現中可能會有所不同。

在源CPython的2.7這是在實施./Python/bltinmodule.c通過builtin_max^[source]，它包裝更一般的函數min_max^[source]。

min_max將迭代通過值，並使用PyObject_RichCompareBool^[docs]以查看它們是否是比電流值越大。如果是這樣，更大的價值取代它。等值將被跳過。

其結果是，第一個最大值將在平局情況下選擇。

Answer 2

從實證檢驗，似乎名單上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') 

而且Jeremy's excellent sleuthing證實，這是確實如此。

Answer 3

你的問題有時會引起注意。在對數據結構進行排序時，爲了比較的目的，經常希望保持被認爲相等的對象的相對順序。這將被稱爲stable sort。

如果您絕對需要此功能，您可以做一個sort()，其中will be stable然後知道相對於原始列表的順序。

根據python本身，我不相信你得到任何保證，當你調用max()時你會得到哪個元素。其他答案給出了cpython的答案，但其他實現（IronPython，Jython）的功能可能不同。

Answer 4

對於Python 2的版本，IMO，我相信你不能假設max()在關係的情況下返回列表中的第一個最大元素。我有這樣的信念，因爲max()應該實現真正的數學函數max，它用於具有總順序的集合上，並且元素沒有任何「隱藏信息」。

（我會假設其他人已經正確研究，並且Python文檔沒有給出max()的任何保證。）

（一般情況下，有問題的無休止的號碼，你可以問一個庫函數的行爲，幾乎所有的人不能回答，比如：多少堆棧空間將max()使用？它會使用SSE嗎？多少臨時內存？它是否可以多次比較同一對對象（如果比較有副作用）？對於「特殊」已知數據結構，它可以比O（n）時間運行更快嗎？等等）

Answer 5

對於Python 3，max()在綁定情況下的行爲不再僅僅是一個實現細節，詳見其他答案。該功能現在保證，作爲Python 3 docs明確說明：

如果有多個項目是最大，該函數返回遇到的第一個 。這與其他排序穩定性保持一致，如sort（iterable，key = keyfunc，reverse = True）[0]和 heapq.nlargest（1，iterable，key = keyfunc）。