Tại sao là "sắp xếp()" chậm hơn so với "bản sao, sau đó .sort()" Python của

Question

Đây là mã tôi chạy:

import timeit 

print timeit.Timer('''a = sorted(x)''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000) 
print timeit.Timer('''a=x[:];a.sort()''', '''x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]''').timeit(number = 1000) 

và đây là kết quả:

0.00259663215837 
0.00207390190177 

Tôi muốn biết tại sao sử dụng .sort() luôn nhanh hơn sắp xếp() mặc dù cả hai đều đang sao chép danh sách?

Lưu ý: Tôi đang chạy Python 2.7 trên một i5 2.53GHz với Win7

Answer 1

Sự khác biệt Bạn đang tìm kiếm tại là rất nhỏ, và hoàn toàn biến mất cho các danh sách dài hơn. Đơn giản chỉ cần thêm * 1000 định nghĩa của x cho kết quả như sau trên máy tính của tôi:

2.74775004387 
2.7489669323 

đoán tốt nhất của tôi với lý do rằng sorted() là hơi chậm cho bạn là sorted() nhu cầu sử dụng một số mã chung mà có thể sao chép bất kỳ lặp lại vào danh sách, trong khi sao chép danh sách trực tiếp có thể giả định rằng nguồn cũng là một danh sách. Mã phân loại được sử dụng bởi CPython thực sự giống nhau đối với list.sort() và sorted(), vì vậy đó không phải là điều gây ra sự khác biệt.

Sửa: Các source code of the current development version of sorted() không tương đương với đạo đức của

a = list(x) 
a.sort() 

và trên thực tế, sử dụng mã này thay vì phiên bản thứ hai của bạn loại bỏ bất kỳ sự khác biệt tốc độ đáng kể cho bất kỳ kích thước danh sách.

Answer 2

Để hỗ trợ @Sven Marnach's answer:

Có một sự khác biệt nhỏ so với danh sách nhỏ:

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]; s=sorted" "a=s(x)" 
1000000 loops, best of 3: 1.87 usec per loop 

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]" "a=x[:];a.sort()" 
1000000 loops, best of 3: 1.66 usec per loop 

Sự khác biệt sẽ biến mất với * 1000 (danh sách lớn hơn):

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000; s=sorted" "a=s(x)" 
100 loops, best of 3: 3.42 msec per loop 

$ python2.7 -mtimeit -s "x = [(2, 'bla'), (4, 'boo'), (3, 4), (1, 2) , (0, 1), (4, 3), (2, 1) , (0, 0)]*1000" "a=x[:];a.sort()" 
100 loops, best of 3: 3.48 msec per loop