Tối đa nào Python chọn trong trường hợp cà vạt?

Question

Khi sử dụng hàm max() trong Python để tìm giá trị lớn nhất trong danh sách (hoặc bộ tuple, dict, v.v.) và có một giá trị lớn nhất, cái nào mà Python chọn? Là nó ngẫu nhiên?

Điều này có liên quan nếu, ví dụ, một danh sách các bộ và một chọn tối đa (sử dụng key=) dựa trên phần tử đầu tiên của bộ túp nhưng có các phần tử thứ hai khác nhau. Python chọn cái nào để chọn tối đa?

Tôi đang làm việc bằng Python v2.6.

Answer 1

Trên Python 2, điều này không được chỉ định trong tài liệu và không nằm trong phần di động trong Python của thư viện chuẩn, vì vậy hành vi này có thể khác nhau giữa các lần triển khai.

Trong nguồn để CPython 2.7 này được thực hiện trong ./Python/bltinmodule.c bởi builtin_max^[source], mà kết thúc tốt đẹp tổng quát hơn min_max chức năng ^[source].

min_max sẽ lặp qua các giá trị và sử dụng PyObject_RichCompareBool^[docs] để xem họ là lớn hơn giá trị hiện tại. Nếu vậy, giá trị lớn hơn sẽ thay thế nó. Các giá trị bằng nhau sẽ bị bỏ qua.

Kết quả là mức tối đa đầu tiên sẽ được chọn trong trường hợp cà vạt.

Answer 2

Từ thử nghiệm thực nghiệm, dường như max() và min() trên một danh sách sẽ trở lại là người đầu tiên trong danh sách mà phù hợp với max()/min() trong trường hợp của một tie:

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

Và Jeremy's excellent sleuthing khẳng định rằng đây là thực sự là trường hợp.

Answer 3

Câu hỏi của bạn phần nào dẫn đến ghi chú. Khi sắp xếp một cấu trúc dữ liệu, thường có một mong muốn giữ trật tự tương đối của các đối tượng được coi là bình đẳng cho các mục đích so sánh. Điều này sẽ được gọi là stable sort.

Nếu bạn hoàn toàn cần tính năng này, bạn có thể thực hiện sort(), trong đó will be stable và sau đó có kiến ​​thức về thứ tự liên quan đến danh sách gốc.

Theo chính python, tôi không tin rằng bạn nhận được bất kỳ sự đảm bảo nào về yếu tố bạn sẽ nhận được khi bạn gọi max(). Các câu trả lời khác đang đưa ra câu trả lời cpython, nhưng các triển khai khác (IronPython, Jython) có thể hoạt động khác nhau.

Answer 4

Đối với phiên bản Python 2, IMO, tôi tin rằng bạn không thể giả định rằng max() trả về phần tử tối đa đầu tiên trong danh sách trong trường hợp quan hệ. Tôi có niềm tin này bởi vì max() là nghĩa vụ phải thực hiện chức năng toán học thực sự max, được sử dụng trên các bộ có tổng số thứ tự và nơi các phần tử không có bất kỳ "thông tin ẩn" nào.

(Tôi giả định rằng những người khác đã nghiên cứu chính xác và tài liệu Python không cung cấp bất kỳ đảm bảo nào cho max().)

(Nói chung, có vô số câu hỏi bạn có thể hỏi về hành vi của hàm thư viện và hầu như tất cả các câu hỏi đều không thể trả lời được. Ví dụ: Bao nhiêu không gian ngăn xếp sẽ max() sử dụng Nó có sử dụng SSE không? Bộ nhớ tạm thời có thể so sánh cùng một cặp đối tượng nhiều hơn một lần (nếu so sánh có tác dụng phụ)? Nó có thể chạy nhanh hơn O (n) cho cấu trúc dữ liệu được biết đến đặc biệt không? .))

Answer 5

Đối với Python 3, hành vi của max() trong trường hợp quan hệ không chỉ là chi tiết triển khai chi tiết trong các câu trả lời khác. Tính năng này hiện được đảm bảo, vì trạng thái rõ ràng là Python 3 docs:

Nếu nhiều mục tối đa, hàm trả về giá trị đầu tiên là . Điều này phù hợp với các công cụ bảo quản phân loại ổn định khác chẳng hạn như được sắp xếp (iterable, key = keyfunc, reverse = True) [0] và heapq.nlargest (1, iterable, key = keyfunc).