Việc sử dụng chuỗi như là chìa khóa trong dict có luôn nhanh hơn không?

Question

Trên số page này, tôi thấy điều gì đó thú vị:

Lưu ý rằng có một đường dẫn nhanh cho các lệnh (thực tế) chỉ xử lý các khóa str; điều này không ảnh hưởng đến độ phức tạp của thuật toán, nhưng nó có thể ảnh hưởng đáng kể đến các yếu tố không đổi: nhanh như thế nào một chương trình điển hình kết thúc.

Vậy điều đó có nghĩa là gì?

Điều đó có nghĩa là sử dụng chuỗi làm khóa luôn luôn nhanh hơn?

Nếu có, tại sao?

Cập nhật:

Cảm ơn những lời đề nghị về tối ưu hóa! Nhưng tôi thực sự quan tâm hơn đến sự thật đơn giản, hơn là liệu chúng ta có nên tối ưu hóa hay không.

Cập nhật 2:

Cảm ơn câu trả lời tuyệt vời, tôi sẽ trích dẫn nội dung từ link cung cấp bởi @DaveWebb đây:

" ...

ma_lookup ban đầu được đặt thành hàm lookdict_string (được đổi tên thành lookdict_unicode trong 3.0), dưới dạng cho rằng cả hai khóa trong từ điển và khóa được tìm kiếm đều là chuẩn PyStringObject. Sau đó, nó có thể thực hiện một vài phép tối ưu hóa, chẳng hạn như giảm thiểu các kiểm tra lỗi khác nhau, vì so sánh chuỗi-to-chuỗi không bao giờ làm tăng ngoại lệ. Cũng không cần so sánh đối tượng phong phú, có nghĩa là chúng ta tránh gọi PyObject_RichCompareBool và luôn sử dụng trực tiếp _PyString_Eq.

... "

Ngoài ra, đối với số thí nghiệm, tôi nghĩ rằng kích thước của phần chênh lệch sẽ còn lớn hơn nếu không có int-to-string chuyển đổi

Answer 1

Mã C làm nền tảng cho Python dict được tối ưu hóa cho các khóa Chuỗi. You can read about this here (và trong cuốn sách mà blog đề cập đến).

Nếu thời gian chạy Python biết dict của bạn chỉ chứa chuỗi khóa, nó có thể làm những việc như không phục vụ cho các lỗi sẽ không xảy ra với chuỗi so sánh chuỗi và bỏ qua toán tử so sánh phong phú. Điều này sẽ làm cho trường hợp phổ biến của chuỗi khóa chỉ dict nhanh hơn một chút. (Cập nhật: thời gian cho thấy nhiều hơn một chút.)

Tuy nhiên, điều này sẽ không làm thay đổi đáng kể thời gian chạy của hầu hết các chương trình Python. Chỉ lo lắng về việc tối ưu hóa này nếu bạn đã đo lường và tìm thấy dict tra cứu là một nút cổ chai trong mã của bạn. As the famous quote says, "Premature optimization is the root of all evil."

Cách duy nhất để xem làm thế nào điều nhanh hơn nhiều thực sự là, là để thời gian họ:

>>> timeit.timeit('a["500"]','a ={}\nfor i in range(1000): a[str(i)] = i') 
0.06659698486328125 
>>> timeit.timeit('a[500]','a ={}\nfor i in range(1000): a[i] = i') 
0.09005999565124512 

Vì vậy, sử dụng các phím chuỗi là khoảng 30% nhanh hơn ngay cả so với int phím, và tôi phải thừa nhận tôi đã ngạc nhiên với kích thước của sự khác biệt.

Answer 2

Vì đây chỉ ảnh hưởng đến Lần duy nhất bạn thực sự cần phải tối ưu hóa là khi bạn đang làm việc với các tập dữ liệu rất lớn - điều này không ảnh hưởng gì đến điều này. nơi bạn có các từ điển nhỏ với các chuỗi làm khóa, Python sẽ nhanh chóng - đây là cách sử dụng phổ biến, vì vậy nó đã được tối ưu hóa cho.

Như Ignacio Vazquez-Abrams chỉ ra, có khả năng chuyển đổi khóa của bạn thành một chuỗi sẽ tốn kém (nhiều hơn) so với mức tăng nhẹ bạn có thể thu được từ đó là chuỗi cho dict.

Trong ngắn hạn sử dụng những gì có liên quan đến tình huống của bạn - tối ưu hóa chỉ nên được thực hiện khi có nhu cầu cho nó, không phải trước đây.

Một số xét nghiệm:

python -m timeit -s "a={key: 1 for key in range(1000)}" "a[500]" 
10000000 loops, best of 3: 0.0773 usec per loop 

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[\"500\"]" 
10000000 loops, best of 3: 0.0452 usec per loop 

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[str(500)]" 
1000000 loops, best of 3: 0.244 usec per loop 

Như bạn có thể thấy, trong khi dict chuỗi dựa trên là nhanh hơn, chuyển đổi phím là rất tốn kém bằng cách so sánh, hoàn toàn giảm thiểu mức tăng (và sau đó một số). Vì vậy, có, nếu dữ liệu bạn đang sử dụng là chỉ được sử dụng làm khóa cho từ điển và định dạng lưu trữ của bạn trong không quan trọng, thì các chuỗi thích hợp hơn trong từ điển nhỏ. Trong thực tế, đó là một trường hợp rất hiếm (và bạn có thể sẽ sử dụng các chuỗi đã).