Từ điển Python tốn bao nhiêu để xử lý?

Question

Như các trạng thái tiêu đề, các từ điển Python tốn kém để xử lý như thế nào? Tạo, chèn, cập nhật, xóa, tất cả.

Độ phức tạp thời gian tiệm cận là điều thú vị, nhưng cũng so sánh chúng với ví dụ như thế nào tuples hoặc danh sách bình thường.

Answer 1

dicts (giống như set s khi bạn không cần liên kết giá trị cho mỗi khóa nhưng chỉ cần ghi lại nếu một khóa hiện diện hoặc vắng mặt) được tối ưu hóa khá nhiều. Tạo một số dict từ khóa N hoặc cặp khóa/giá trị là O(N), tìm nạp là O(1), đặt được khấu hao O(1), v.v. Không thể thực sự làm bất cứ điều gì tốt hơn đáng kể cho bất kỳ container không nhỏ nào!

Đối với các thùng chứa nhỏ, bạn có thể dễ dàng kiểm tra ranh giới với timeit điểm chuẩn dựa trên. Ví dụ:

$ python -mtimeit -s'empty=()' '23 in empty' 
10000000 loops, best of 3: 0.0709 usec per loop 
$ python -mtimeit -s'empty=set()' '23 in empty' 
10000000 loops, best of 3: 0.101 usec per loop 
$ python -mtimeit -s'empty=[]' '23 in empty' 
10000000 loops, best of 3: 0.0716 usec per loop 
$ python -mtimeit -s'empty=dict()' '23 in empty' 
10000000 loops, best of 3: 0.0926 usec per loop 

điều này cho thấy việc kiểm tra tư cách thành viên trong danh sách trống hoặc bộ dữ liệu nhanh hơn 20-30 nano giây so với việc kiểm tra tư cách thành viên trong nhóm hoặc bộ trống; khi mỗi nano giây đều quan trọng, thông tin này có thể có liên quan đến bạn. Di chuyển lên một chút ...:

$ python -mtimeit -s'empty=range(7)' '23 in empty' 
1000000 loops, best of 3: 0.318 usec per loop 
$ python -mtimeit -s'empty=tuple(range(7))' '23 in empty' 
1000000 loops, best of 3: 0.311 usec per loop 
$ python -mtimeit -s'empty=set(range(7))' '23 in empty' 
10000000 loops, best of 3: 0.109 usec per loop 
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '23 in empty' 
10000000 loops, best of 3: 0.0933 usec per loop 

bạn thấy rằng đối với 7 mặt hàng container (không bao gồm một trong những lợi ích) cán cân hiệu suất đã thay đổi, và bây giờ dicts và bộ có những ưu điểm bởi hàng trăm nano giây . Khi mặt hàng quan tâm IS hiện diện:

$ python -mtimeit -s'empty=range(7)' '5 in empty' 
1000000 loops, best of 3: 0.246 usec per loop 
$ python -mtimeit -s'empty=tuple(range(7))' '5 in empty' 
1000000 loops, best of 3: 0.25 usec per loop 
$ python -mtimeit -s'empty=dict.fromkeys(range(7))' '5 in empty' 
10000000 loops, best of 3: 0.0921 usec per loop 
$ python -mtimeit -s'empty=set(range(7))' '5 in empty' 
10000000 loops, best of 3: 0.112 usec per loop 

bộ và bộ không đạt được nhiều, nhưng bộ và danh sách làm, mặc dù dicts và thiết lập vẫn nhanh hơn rất nhiều.

Và cứ tiếp tục như vậy - timeit giúp dễ dàng chạy các tiêu chuẩn vi mô (nói đúng, bảo đảm chỉ trong những trường hợp cực kỳ hiếm hoi mà nano giây KHÔNG quan trọng, nhưng, dễ thực hiện, không lớn khó khăn để kiểm tra các trường hợp KHÁC ;-).

Answer 2

Từ điển là một trong những phần được điều chỉnh nhiều hơn của Python, vì chúng làm giảm quá nhiều ngôn ngữ. Ví dụ, các thành viên của một lớp và các biến trong một khung ngăn xếp đều được lưu trữ nội bộ trong các từ điển. Chúng sẽ là lựa chọn tốt nếu chúng là cấu trúc dữ liệu đúng.

Lựa chọn giữa các danh sách và chữ cái dựa trên hiệu suất có vẻ lạ: chúng làm những việc khác nhau. Có thể bạn có thể cho chúng tôi biết thêm về vấn đề bạn đang cố giải quyết.