Hướng dẫn how dictionary works under the hood in python - cách từ điển hoạt động dưới mui xe trong python
Mục lụcBạn có phải là nhà phát triển Python mong muốn tìm hiểu thêm về nội bộ của ngôn ngữ và để hiểu rõ hơn về cách các bảng băm python và cấu trúc dữ liệu hoạt động? Hoặc có thể bạn có kinh nghiệm trong các ngôn ngữ lập trình khác và muốn hiểu làm thế nào và các bảng băm được thực hiện trong Python? Bạn đã đến đúng nơi! Show
Đến cuối bài viết này, bạn sẽ có một sự hiểu biết về:
Hướng dẫn này nhằm vào các nhà phát triển Python trung gian và thành thạo. Nó giả định sự hiểu biết cơ bản về từ điển và bộ Python. Hãy cùng đi sâu vào việc nhìn vào bàn băm Python! Học những điều cơ bản của bảng bămTrước khi đi sâu vào các chi tiết triển khai Python, trước tiên bạn cần hiểu các bảng băm là gì và cách sử dụng chúng. Bảng băm là gìBạn đã bao giờ nghĩ về cách lưu trữ từ điển Python trong bộ nhớ chưa? Bộ nhớ trong máy tính của chúng tôi có thể được coi là một mảng đơn giản với các chỉ mục số:  Vậy làm thế nào mà Python biết giá trị nào thuộc về khóa nào, khi sử dụng các khóa không số? Giải pháp đơn giản nhất là có mỗi phần tử trong mảng lưu trữ cả khóa và giá trị, lặp qua mảng và kiểm tra phần tử theo phần tử, cho đến khi tìm một phần chứa khóa chứa khóa mong muốn. Giải pháp này không phải là hiệu quả hoàn hảo, vì nó sẽ yêu cầu lặp đi lặp lại qua mảng nhiều lần - và đây là nơi các bảng băm đến chơi. Bảng băm là một cấu trúc được thiết kế để lưu trữ một danh sách các cặp giá trị khóa, mà không ảnh hưởng đến tốc độ và hiệu quả của việc thao túng và tìm kiếm cấu trúc. Bảng băm sử dụng hàm băm để tính toán một chỉ mục, thành một mảng các khe cắm, từ đó có thể tìm thấy giá trị mong muốn.hash function to compute an index, into an array of slots, from which the desired value can be found. Làm thế nào để một hàm băm hoạt độngChức năng băm, ở dạng đơn giản nhất, là một hàm tính toán chỉ mục của cặp giá trị khóa-để bạn có thể nhanh chóng chèn, tìm kiếm và xóa các phần tử trong mảng bộ nhớ của bạn. Bạn nên bắt đầu với một ví dụ đơn giản: một đối tượng giống như từ điển, chứa 3 sản phẩm và số lượng hàng tồn kho của chúng. Đối với hàm băm, bạn sẽ cần một phương thức để biến các phím chuỗi thành các giá trị số để bạn có thể nhanh chóng tra cứu chúng trong bộ nhớ. Hãy tự mình thử nó Cố gắng nghĩ về một thao tác đơn giản để thực hiện trên các giá trị chuỗi để biến chúng thành các giá trị số. Hiển thị giải pháp Có nhiều phương pháp để đạt được điều đó. Làm thế nào về việc tính độ dài của mỗi khóa? Vì vậy, bạn đã quyết định tính toán độ dài của các giá trị chuỗi, tuyệt vời! Don Tiết quên rằng các giá trị số phải nằm trong vòng 0 đến 3 để chúng phù hợp với bên trong mảng 3 phần tử. Bạn có thể sử dụng toán tử modulo về độ dài cho điều đó: Ví dụ, Tiếng hoan hô! Bạn chỉ cần xây dựng bàn băm đầu tiên của bạn! Giữ trong một giây ở đó. Điều gì xảy ra khi hai phím có cùng chiều dài? Bạn đã thắng được có thể chèn cả hai ở cùng một chỉ số. Điều này được gọi là va chạm băm.hash collision. Cách xử lý va chạmVa chạm băm thực tế là không thể tránh khỏi khi băm một tập hợp ngẫu nhiên của một tập hợp lớn các phím có thể. Có nhiều chiến lược để xử lý va chạm - tất cả đều yêu cầu các khóa được lưu trữ trong bảng, cùng với các giá trị liên quan. Hai trong số những cái phổ biến nhất là địa chỉ mở và chuỗi riêng biệt.Open Addressing and Separate Chaining.
John và Lisa va chạm kể từ khi cả hai băm với chỉ số
Lần này, Sandra Dee đã không va chạm với Sandra vì mỗi phần tử giữ một con trỏ đến một loạt các bản ghi va chạm. Hiểu bảng băm PythonKhi bạn nghĩ về nó, các khóa từ điển Python cho phép nhiều loại hơn là chỉ số nguyên. Chúng có thể là chuỗi, chức năng, và nhiều hơn nữa. Làm thế nào để Python lưu trữ các phím này bên trong bộ nhớ và biết nơi để tìm giá trị của chúng? Bạn đoán đúng - bàn băm! Python thực hiện các bảng băm dưới mui xe, một triển khai hoàn toàn không thể đối với bạn với tư cách là một nhà phát triển. Tuy nhiên, nó có thể được sử dụng tuyệt vời để bạn hiểu cách thực hiện các bảng băm python, tối ưu hóa của chúng và cách sử dụng chúng một cách khôn ngoan. Hãy cùng đi sâu vào một số bên trong để hiểu rõ hơn về cách tất cả các khái niệm mới mà bạn vừa học được được đưa vào thực hành. Khám phá chức năng băm pythonChức năng băm Python lấy một đối tượng băm và băm thành 32/64 bit (phụ thuộc vào kiến trúc hệ thống). Các bit được phân phối tốt như có thể thấy trong ví dụ sau, cho thấy hai chuỗi rất giống nhau - chuỗi liên tiếp, liên tiếp, thường được sử dụng trong từ điển, với các giá trị băm rất khác nhau: Phân phối này làm giảm tỷ lệ va chạm băm, từ đó làm cho từ điển nhanh hơn nhiều. Hơn nữa, bạn nên biết rằng giá trị băm chỉ không đổi cho trường hợp hiện tại của quy trình. Bạn có thể đã vấp ngã khi băm khác nhau của cùng một đối tượng và tự hỏi tại sao nó lại xảy ra. Lý do chính cho hiện tượng này có liên quan đến bảo mật: các bảng băm dễ bị ảnh hưởng bởi các cuộc tấn công dos va chạm khi sử dụng các giá trị băm không đổi. Python 3.6 đã giới thiệu việc thực hiện Siphash để ngăn chặn các cuộc tấn công này. Bạn có thể đọc thêm về nó trên PEP 456. Sau đây thể hiện các băm khác nhau trên hai lần chạy khác nhau: Xử lý va chạm trong PythonPython sử dụng địa chỉ mở để giải quyết các trường hợp băm. Mã nguồn Python Suggets rằng địa chỉ mở được ưu tiên hơn chuỗi vì chi phí liên kết để chuỗi sẽ là đáng kể. Trước đó, bạn đã thấy một ví dụ về thăm dò tuyến tính. Python sử dụng thăm dò ngẫu nhiên, như có thể thấy trong mã nguồn hoặc trong mã Python rất đơn giản này:open addressing to resolve hash coliisions. Python source code suggets that open addressing is preferred over chaining since the link overhead for chaining would be substantial. Earlier, you’ve seen an example of linear probing. Python uses random probing, as can be seen in the source code, or in this very simplified Python code: Giống như thăm dò tuyến tính, phần đầu tiên của thuật toán này tiến hành một cách cố định ( Xóa các phần tử bằng các giá trị giảTrong một thế giới hoàn hảo không có va chạm, việc xóa các phần tử sẽ đơn giản: chỉ cần xóa phần tử ở chỉ mục mong muốn để nó có thể được nạp lại với các giá trị khác. Thật không may, chúng ta không sống trong một thế giới hoàn hảo, và các vụ va chạm xảy ra thường xuyên. Bạn có nhớ ví dụ địa chỉ mở từ trước không? Bây giờ giả sử bạn muốn xóa John Smith khỏi bàn. Có vẻ tầm thường, phải không? Hash John Smith và xóa phần tử nằm ở chỉ số tính toán. Bây giờ, bạn có thể đã nhận thấy vấn đề trong phương pháp này. Sau khi xóa John, Sandra là không thể truy cập! Băm Sandra sẽ đưa chúng ta đến một khe trống. Vì lý do chính xác này, Python thực hiện các giá trị giả - thay vì xóa hoàn toàn phần tử John, nó sẽ đặt một giá trị giả cố định ở đó. Khi thuật toán phải đối mặt với một giá trị giả, nó biết rằng có một giá trị ở đó nhưng nó đã bị xóa. Sau đó, nó tiếp tục thăm dò về phía trước. Thực hiện mọi thứ với PythonBây giờ bạn đã biết các bảng băm là gì, chức năng băm python hoạt động như thế nào và Python xử lý va chạm như thế nào, đã đến lúc thấy những điều này hoạt động bằng cách khám phá việc thực hiện từ điển và phương pháp tra cứu. Phương pháp tra cứu được sử dụng trong tất cả các hoạt động: tìm kiếm, chèn và xóa. Điều đầu tiên bạn cần biết là Python khởi tạo một dict với một mảng 8 phần tử. Các thí nghiệm cho thấy kích thước này đủ cho hầu hết các dicts phổ biến, thường được tạo để vượt qua các đối số từ khóa. Mỗi phần tử trong mảng chứa một cấu trúc chứa khóa, giá trị và băm. Hash được lưu trữ để không tính toán lại với mỗi lần tăng kích thước của từ điển (được giải thích thêm trong việc khám phá các bảng Hash Hash tối ưu hóa: Thay đổi kích thước từ điển). Ghi chú Cho đến bây giờ, các chỉ số bộ nhớ được hiển thị dưới dạng các giá trị thập phân. Từ thời điểm này trở đi, bạn sẽ nhận thấy rằng các địa chỉ bộ nhớ sẽ được hiển thị dưới dạng số nguyên nhị phân. Don Tiết được sợ hãi! Bạn có thể tiếp tục đọc ngay cả khi bạn không quen thuộc với họ - Tôi chỉ sử dụng nó để bạn hiểu rõ hơn về cách các bảng Hash Python hoạt động với các bit, nhưng nó không bắt buộc phải hiểu điều đó. Trên phương pháp tra cứu. Ở đây, một phiên bản Python đơn giản hóa, tiếp theo là một lời giải thích:
Nếu bạn đã viết hoạt động tìm kiếm, nó sẽ xem xét các dòng sau: Như tôi đã đề cập trước đây, việc xử lý Kiểm tra hiểu Hoạt động chèn sẽ sử dụng chỉ số nhận được từ phương thức tra cứu ngay cả khi phần tử là Hiển thị giải pháp Đúng! Phương pháp chèn sẽ rất vui khi nhận được một khe trống - điều đó có nghĩa là không có va chạm băm nào liên quan đến quá trình này. Hiểu bộ PythonCùng với từ điển, các bảng băm Python cũng đóng vai trò là cấu trúc cơ bản cho các bộ. Cả hai triển khai đều khá giống nhau như có thể thấy trong mã nguồn, ngoại trừ việc đặt không lưu trữ giá trị cho từng khóa, có nghĩa là tối ưu hóa của Python, được hiển thị sau trong bài viết này, không áp dụng cho chúng. Việc sử dụng các bảng băm cho các bộ làm cho hoạt động tra cứu, được sử dụng thường xuyên trong các bộ để giữ chúng mà không cần sao chép, khá nhanh (như bạn nên biết bây giờ - nó luôn phụ thuộc vào sự va chạm). Khám phá Tối ưu hóa bảng Hash PythonCác phương pháp trên không hoàn toàn giống với Python. Tôi đã không muốn quá tạo thành mọi thứ, vì vậy tôi đã bỏ qua một số chi tiết làm cho từ điển Python rực rỡ nhanh chóng. Phần sau đây sẽ hướng dẫn bạn xây dựng một từ điển tùy chỉnh, thực hiện các tối ưu hóa của các bảng băm Python. Bước đầu tiên của bạn là tạo một lớp Bạn sẽ sớm điền vào các phương pháp này. Lưu ý rằng Hãy để Lặn đi vào các tối ưu hóa bàn băm Python! Từ điển nhỏ gọnTừ điển nhỏ gọn tối ưu hóa không gian có băm các bảng chiếm. Trước khi chúng được thực hiện, Python đã có các bảng băm thưa thớt - mỗi khe không có người ở lại chiếm nhiều không gian như một khe chiếm vì nó phải tiết kiệm không gian cho chìa khóa, băm và giá trị. Từ điển nhỏ gọn đã giới thiệu một bảng nhỏ hơn nhiều chỉ cho các chỉ số và một bảng riêng cho các khóa, giá trị và băm. Bằng cách này, bảng chỉ số có thể là cái thưa thớt trong khi bảng lớn hơn dày đặc. Ví dụ, trước các từ điển nhỏ gọn, sau đây là cách từ điển và mảng bộ nhớ tương ứng của nó trông giống như (được lấy từ văn bản Raymond Hettinger,): Thay vào đó, với từ điển nhỏ gọn, hai bảng khác nhau được xây dựng: Lấy Timmy làm ví dụ. Nó được băm vào chỉ số thứ 5, trong đó chứa số Raymond Hettinger, người tạo ra từ điển nhỏ gọn, cho biết:
Phần mã này chèn các phần tử mới vào từ điển và kiểm tra kích thước sau mỗi lần chèn cho đến khi nó đạt được 1000 phần tử. Tại đây, cách thức kích thước từ điển nhỏ gọn Python 3.8 so với Python 2.7 Từ điển không nhỏ gọn: Từ điển:
Để thực hiện tính năng này trong từ điển tùy chỉnh của bạn, từ điển cần triển khai hai mảng tách biệt: một cho các chỉ số và một cho các mục thực tế. Trước khi bạn làm điều đó, có những tối ưu hóa khác để xem xét, do đó, việc triển khai cuối cùng sẽ diễn ra sớm, trong việc kết hợp tất cả lại với nhau. Trong khi đó, bạn có thể tạo phương thức xây dựng mảng chỉ số và khởi tạo lớp với các biến
Ghi chú Từ điển nhỏ gọn đã được thực hiện trong Python 3.6. Từ điển chia sẻ chínhPython 3.3 giới thiệu từ điển chia sẻ khóa. Khi từ điển được tạo ra để lấp đầy khe mô tả của một đối tượng, chúng được tạo ở dạng phân chia. Bảng khóa được lưu trong bộ nhớ cache trong loại, có khả năng cho phép tất cả các từ điển thuộc tính của các trường hợp của một lớp chia sẻ các khóa. Hành vi này xảy ra trong phương pháp Visual sau đây cho thấy ba trường hợp của cùng một lớp: Bạn có thể thấy rằng mỗi trường hợp chỉ giữ các giá trị của nó, trong khi có một vị trí được chia sẻ duy nhất trong bộ nhớ cho các khóa. Hãy để thực hiện tính năng tuyệt vời này trong từ điển của bạn:
Từ điển thay đổi kích thướcPython kiểm tra kích thước bảng mỗi khi chúng tôi thêm một phím và nếu bảng là hai phần ba, nó sẽ thay đổi kích thước bảng băm. Nếu một từ điển có 50000 khóa hoặc ít hơn, kích thước mới là
Phiên bản từ điển riêngPython 3.6 đã thêm một phiên bản riêng tư mới vào từ điển, tăng lên ở mỗi lần tạo từ điển và tại mỗi thay đổi từ điển. Cơ sở lý luận là bỏ qua các tra cứu từ điển nếu phiên bản không thay đổi và thay vào đó sử dụng các giá trị được lưu trong bộ đệm. Việc thực hiện của bạn có thể thực hiện một phiên bản cho mỗi trường hợp, mặc dù nó đã giành được thực hiện bộ nhớ đệm thực tế của các giá trị.
Để tất cả chúng cùng nhauGhi chú Mã đầy đủ có thể được tìm thấy ở đây. Đó là thời gian để sử dụng tất cả các phương pháp mới tuyệt vời này và làm cho từ điển của bạn có thể sử dụng được!
1 class Dictionary:
2
3 def __init__(self, *args, **kwargs):
4 """Dict initializiation"""
5
6 @staticmethod
7 def _generate_probes(hash_: int, mask: int) -> Iterable[int]:
8 index = hash_ & mask
9 yield index
10 perturb = hash_
11 while True:
12 new_hash = index * 5 + 1 + perturb
13 yield new_hash & mask
14 perturb >>= 5
15
16 def _lookup(self, key: Any, hashvalue: int) -> Tuple[int, Any]:
17 """The lookup method"""
18
19 def __getitem__(self, key: Any) -> Any:
20 """Get value from dict"""
21
22 def __setitem__(self, key: Any, value: Any):
23 """Insert item to dict"""
24
25 def __delitem__(self, key: Any):
26 """Delete item from dict"""
27
28 def __len__(self) -> int:
29 """Dict length"""
30
31 def __iter__(self) -> Iterable:
32 """Iterate through dictionary"""
33
34 def __contains__(self, key: Any) -> bool:
35 """Check if dictionary contains a key"""
36
37 def __repr__(self) -> str:
38 """Dict representation"""
|
