Tại sao chậm hơn tối đa so với sắp xếp?

Question

Tôi đã phát hiện ra rằng max là chậm hơn so với sort hàm trong Python 2 và 3.

Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]' 
1000 loops, best of 3: 239 usec per loop 
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'   
1000 loops, best of 3: 342 usec per loop 

Python 3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]' 
1000 loops, best of 3: 252 usec per loop 
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)' 
1000 loops, best of 3: 371 usec per loop 

Tại sao làmax (O(n)) chậm hơn chức năng sort (O(nlogn))?

Answer 1

Bạn phải rất cẩn thận khi sử dụng mô-đun timeit bằng Python.

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]' 

Ở đây mã khởi tạo chạy một lần để tạo một mảng ngẫu nhiên a. Sau đó, phần còn lại của mã được chạy nhiều lần. Lần đầu tiên nó sắp xếp mảng, nhưng mỗi lần bạn gọi phương thức sắp xếp trên một mảng đã được sắp xếp. Chỉ có thời gian nhanh nhất được trả về, vì vậy bạn đang thực sự định thời gian để Python sắp xếp một mảng đã sắp xếp.

Một phần thuật toán sắp xếp của Python là phát hiện khi mảng đã được sắp xếp một phần hoặc hoàn toàn. Khi hoàn toàn sắp xếp nó chỉ đơn giản là phải quét một lần thông qua các mảng để phát hiện này và sau đó nó dừng lại.

Nếu thay vào đó bạn cố gắng:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]' 

thì loại xảy ra trên tất cả các vòng lặp thời gian và bạn có thể thấy rằng thời gian để phân loại một mảng thực sự là còn nhiều hơn là chỉ cần tìm giá trị lớn nhất.

Edit: @ skyking của answer giải thích phần tôi rời không giải thích được: a.sort() biết nó đang làm việc trên một danh sách để có thể trực tiếp truy cập vào các yếu tố. max(a) hoạt động trên bất kỳ khả năng lặp nào tùy ý, do đó phải sử dụng lặp lại chung.

Answer 2

Điều này có thể là do l.sort là thành viên của list trong khi max là một chức năng chung. Điều này có nghĩa là l.sort có thể dựa vào biểu diễn nội bộ của list trong khi max sẽ phải trải qua giao thức lặp chung.

Điều này làm cho mỗi thành phần tìm nạp l.sort nhanh hơn mỗi lần tìm nạp phần tử mà max thực hiện.

Tôi giả sử rằng nếu bạn thay vì sử dụng sorted(a), bạn sẽ nhận được kết quả chậm hơn max(a).

Answer 3

Trước hết, lưu ý rằng max() uses the iterator protocol, trong khi list.sort() uses ad-hoc code. Rõ ràng, bằng cách sử dụng một iterator là một chi phí quan trọng, đó là lý do tại sao bạn đang quan sát sự khác biệt về thời gian.

Tuy nhiên, ngoài ra, các thử nghiệm của bạn không công bằng. Bạn đang chạy a.sort() trên cùng một danh sách nhiều lần. Các algorithm used by Python được thiết kế đặc biệt để được nhanh chóng cho đã được (một phần) dữ liệu được sắp xếp. Các thử nghiệm của bạn đang nói rằng thuật toán đang làm tốt công việc của nó.

Đây là những bài kiểm tra công bằng:

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a[:])' 
1000 loops, best of 3: 227 usec per loop 
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a[:].sort()' 
100 loops, best of 3: 2.28 msec per loop 

Ở đây tôi là tạo ra một bản sao của danh sách mỗi lần. Như bạn có thể thấy, thứ tự của các kết quả khác nhau: vi - mili giây, như chúng ta mong đợi.

Và hãy nhớ: big-Oh chỉ định giới hạn trên! Giới hạn dưới cho thuật toán sắp xếp của Python là Ω (n). Là O (n nhật ký n) không tự động ngụ ý rằng mọi lần chạy đều mất một thời gian tỷ lệ thuận với n log n. Nó thậm chí không ngụ ý rằng nó cần phải chậm hơn một thuật toán O (n), nhưng đó là một câu chuyện khác. Điều quan trọng cần hiểu là trong một số trường hợp thuận lợi, thuật toán O (n nhật ký n) có thể chạy trong thời gian O (n) hoặc ít hơn.