tại sao toán tử 'in' với tuple là khóa trong python quá chậm?

Question

Tôi có một dict như:

d=dict() 
d[('1','2')] = 'value' 

Sau đó, tôi truy vấn chính:

if (k1,k2) in d.keys(): 

Khi có triệu bản, tốc độ là một sự đau khổ, bất kỳ vấn đề với các 'trong' điều hành?

Có tìm kiếm tuần tự không?

Tôi phải đặt đường nối là chìa khóa để bỏ qua vấn đề này.

Answer 1

Bạn nên sử dụng

(k1,k2) in d 

thay vì gọi d.keys().

Thực hiện theo cách của bạn, trong Python 2 sẽ dẫn đến tìm kiếm tuyến tính và thay vào đó phủ nhận lợi ích của số dict. Trong Python 3 mã của bạn là hiệu quả (xem ý kiến ​​dưới đây) nhưng phiên bản của tôi là rõ ràng hơn.

Answer 2

Ngoài việc bổ sung cho Nolen Royalty, tôi nghĩ tôi sẽ lưu ý rằng bạn thực sự có thể thực hiện các bài kiểm tra timeit theo cách tốt hơn một chút. Bằng cách di chuyển việc xây dựng các dict vào một chức năng thiết lập, chúng tôi chỉ có thể thời gian hoạt động trên dict, cho chúng ta một kết quả mà chúng ta có thể so sánh dễ dàng.

Trong 3.2:

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys()' '_ = (1, 2) in d.keys()' 
1000000 loops, best of 3: 0.404 usec per loop 

python -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d' 
1000000 loops, best of 3: 0.247 usec per loop 

Bạn có thể thấy sự khác biệt. Trong 3.x, làm việc trực tiếp trên dict mang đến cho chúng ta tốc độ tăng gần gấp 2 lần, điều này không tệ.

Trong 2.7.3:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d.keys(); _ = (1, 2) in d.keys()' 
10 loops, best of 3: 36.3 msec per loop 

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' '_ = ("1", "2") in d' '_ = (1, 2) in d' 
10000000 loops, best of 3: 0.197 usec per loop 

Trong 2.x, sự khác biệt thực sự là đáng kinh ngạc . Sử dụng dict.keys() mất 36,300 micro giây, trong khi chỉ dict mất dưới 0,2 micro giây. Đó là gần hai trăm nghìn lần nhanh hơn.

Chỉ cần nghĩ rằng đó là đáng lưu ý.

Chỉnh sửa:

Tim đã đưa ra nhận xét thú vị, vì vậy tôi đã quyết định làm thử nghiệm kiểm tra. Tôi đã cố gắng chỉ xây dựng danh sách, và sau đó chỉ cần làm việc tra cứu băm, kết quả như sau:

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' 'd.keys()' 'd.keys()' 
100 loops, best of 3: 5.84 msec per loop 

python2 -m timeit -s 'd = {(str(i), str(j)):"a" for i in range(100) for j in range(1000)}' -s 'l=d.keys()' '_ = ("1", "2") in l' '_ = ("1", "2") in l' 
10 loops, best of 3: 25.3 msec per loop 

Bạn có thể thấy rằng trên một dict lớn như thế này, xây dựng danh sách mất khoảng 1/6 thời gian, làm tìm kiếm thông qua danh sách 5/6 của thời gian.