Cái nào nhanh hơn được đặt hoặc từ điển trong python?
Như Wikipedia cho biết “ Kiểm tra tư cách thành viên với các bộ và từ điển nhanh hơn nhiều, O(1), so với tìm kiếm theo trình tự, O(n). Khi kiểm tra “a trong b”, b phải là một tập hợp hoặc từ điển thay vì danh sách hoặc bộ. ” Show
Chắc hẳn bạn đã sử dụng tập hợp thay cho danh sách bất cứ khi nào tốc độ là quan trọng trong mã của bạn, nhưng bạn đã bao giờ tự hỏi tại sao tập hợp lại nhanh hơn nhiều so với danh sách chưa?. Vì vậy, hãy xem chính xác những gì đang diễn ra đằng sau hậu trường trong python để làm cho các bộ nhanh hơn? Các tập hợp được triển khai bằng cách sử dụng bảng băm, Vì vậy, bất cứ khi nào bạn thêm một đối tượng vào một tập hợp, vị trí trong bộ nhớ của đối tượng Và khi kiểm tra tư cách thành viên, tất cả những gì cần làm về cơ bản là xem liệu đối tượng có ở vị trí được xác định bởi hàm băm của nó hay không, vì vậy tốc độ của thao tác này không phụ thuộc vào kích thước của tập hợp Ngược lại, đối với danh sách, toàn bộ danh sách cần được tìm kiếm, điều này sẽ trở nên chậm hơn khi danh sách phát triển Hãy hiểu điều này thông qua một ví dụ
Danh sách Python được triển khai dưới dạng dynamic arrays và các bộ được triển khai dưới dạng hash tables.Bạn phải giữ một điều quan trọng nhất trong tâm trí của bạn. các tập hợp đó không nhanh hơn các danh sách nói chung — kiểm tra tư cách thành viên sẽ nhanh hơn đối với các tập hợp và việc xóa một phần tử cũng vậy và Miễn là bạn không cần các thao tác này, các danh sách thường nhanh hơn Và khi bạn tìm hiểu sâu hơn về điều này, bạn sẽ biết rằng đặt so với. danh sách phụ thuộc phần lớn vào hoạt động chúng tôi đang thực hiện như thế nào,
Ghi chú. Các tập hợp không nhanh hơn các danh sách nói chung — kiểm tra tư cách thành viên nhanh hơn đối với các tập hợp và việc xóa một phần tử cũng vậy. Miễn là bạn không cần những thao tác này, danh sách thường nhanh hơn Trong bài đăng trên blog này, chúng ta sẽ thảo luận về cấu trúc dữ liệu Python, dict và set. Bộ và Từ điển là cấu trúc dữ liệu được ưu tiên khi dữ liệu không có thứ tự nội tại và mỗi dữ liệu có một đối tượng duy nhất để tham chiếu nó. Đối với dict, đối tượng tham chiếu được gọi là khóa và dữ liệu được tham chiếu được gọi là giá trị, đối tượng tham chiếu được sử dụng rộng rãi là loại chuỗi, nhưng bất kỳ loại có thể băm nào cũng hợp lệ. Trong khi set là một bộ sưu tập khóa duy nhất Ảnh của Markus Spiske trên BaptLoại có thể bămLoại có thể băm là những đối tượng thực hiện chức năng __hash__. Hàm băm trả về một giá trị số nguyên cho đối tượng (chuỗi, số nguyên, số float) được truyền cho nó. Giá trị số nguyên giúp tra cứu nhanh trong dict Trong bài đăng trên blog trước, Python — Lists vs Tuples, tôi đã đề cập đến trường hợp tốt nhất để tra cứu trong danh sách hoặc bộ dữ liệu là O(log n) dựa trên Tìm kiếm nhị phân. Trong dict và set, việc tra cứu phần tử mất một khoảng thời gian không đổi là O(1), vì việc tìm kiếm dựa trên chỉ mục tùy ý. Tốc độ trong dict và set đạt được bằng cách sử dụng bảng băm địa chỉ mở làm cấu trúc dữ liệu cơ bản của nó Từ điển và Bộ — Sử dụngđọc chính tảXem xét một danh bạ với danh sách tên và số điện thoại. Để tìm số điện thoại của một người, chiến lược chung để tra cứu trong danh sách hoặc cấu trúc dữ liệu bộ thực hiện theo bước sau
Khi ở trong dict, chúng ta có thể lưu trữ tên người làm khóa và số điện thoại làm giá trị. Phải mất O(1) để tìm số điện thoại. Trong dict, chúng ta có thể lấy số điện thoại bằng cách tra cứu tên người, tên này là duy nhất. Nó không yêu cầu lặp qua tất cả các tên BộXem xét một yêu cầu để tìm tổng số tên duy nhất, nếu dữ liệu được lưu trữ trong danh sách hoặc bộ dữ liệu, nó yêu cầu nhiều vòng lặp for, điều này làm cho độ phức tạp về thời gian là O(n²) Sử dụng Danh sách hoặc Tuples def list_unique_names(phonebook):
Sử dụng phương pháp thiết lập def set_unique_names(phonebook):
Có thể thấy tác động của việc sử dụng cấu trúc dữ liệu sai khi chúng ta sử dụng điện thoại lớn và lặp lại các mục >>> %timeit list_unique_names(large_phonebook) Thuật toán thiết lập nhanh hơn 252 lần so với danh sách, nó sáng Để đạt được tốc độ này, dict và set sử dụng các bảng băm. Bảng băm được lấp đầy bằng cách sử dụng hàm băm, hàm này khéo léo biến khóa tùy ý thành một chỉ mục để tìm nạp giá trị được lưu trữ trên khóa đó Chèn và thay đổi kích thướcĐể tạo một dict hoặc bất kỳ cấu trúc dữ liệu nào khác, chúng ta cần phân bổ một đoạn bộ nhớ hệ thống cho nó. Và để chèn vào dict thì vị trí chèn hay chỉ số phụ thuộc vào dữ liệu. Trong khi chèn, khóa được băm và ẩn để biến thành một số nguyên hiệu quả phù hợp với kích thước bộ nhớ được phân bổ cho nó
Khi một dict hoặc set được khởi tạo, kích thước mặc định được gán là 8, i. e. nghĩa là một bảng băm có kích thước 8 được tạo và khi có nhiều mục hơn được thêm vào dict/set, Python sẽ kiểm tra xem 2/3 kích thước có được lấp đầy hay không, nếu có, thì nó sẽ tăng kích thước của dict/set lên gấp 3 lần. Việc thay đổi kích thước xảy ra mỗi khi chính tả được lấp đầy hai phần ba. Các kích thước có thể thay đổi của dict như sau 8; 18; 39; 81; 165; 333; 669; 1,341; 2,685; 5,373; 10,749; 21,501; 43,005; … Từ điển & Không gian tênKhi biến, hàm hoặc mô-đun được gọi trong Python, một hệ thống phân cấp tra cứu đối tượng sẽ xảy ra, việc duy trì hệ thống phân cấp đó được thực hiện bởi Namespace Management. Việc tra cứu trong quản lý không gian tên phụ thuộc rất nhiều vào từ điển Khi một đối tượng được gọi trong Python, hệ thống phân cấp tra cứu bắt đầu, trước tiên, nó kiểm tra mảng local(), đây không phải là từ điển và nếu nó không tồn tại ở đó, thì hệ thống phân cấp sẽ được chuyển sang mảng global(), nếu . Điều quan trọng cần lưu ý là mặc dù local() và global() là các từ điển rõ ràng, nhưng __builtin__ là một đối tượng mô-đun và việc tra cứu trong các đối tượng dựng sẵn cũng giống như tra cứu từ điển trong bản đồ local() Tra cứu không gian tên ví dụimport math Mã byte được tạo bằng mô-đun dis Mã byte cho ba bài kiểm traTrong test1, hàm sin được gọi rõ ràng bằng cách xem thư viện toán học. Từ bytecode được tạo ra, chúng ta có thể thấy, có hai quá trình tra cứu từ điển xảy ra, một là tìm mô-đun toán học và sau đó tìm hàm sin bên trong nó Trong test2, hàm sin được nhập từ thư viện toán học, làm cho nó có sẵn trong không gian tên chung, thay vì tìm mô-đun toán học rồi tìm hàm sin bên trong nó, chúng ta cần tìm kiếm hàm sin trong không gian tên chung. Do đó nó giúp giảm thời gian thực hiện
Trong test3, hàm sin được định nghĩa trong định nghĩa hàm theo mặc định làm đối số từ khóa và như đã đề cập trước đó, lần tra cứu đầu tiên được thực hiện trên mảng local(), đây không phải là tra cứu từ điển và mảng local() là một mảng nhỏ có . Thời gian thực hiện của test3 nhanh nhất so với tất cả các thử nghiệm khác Với suy nghĩ này, một giải pháp dễ đọc hơn sẽ là đặt một biến cục bộ với tham chiếu toàn cục trước khi vòng lặp bắt đầu. Chúng ta sẽ vẫn phải thực hiện tra cứu toàn cầu một lần bất cứ khi nào hàm được gọi, nhưng tất cả các lệnh gọi đến hàm đó trong vòng lặp sẽ được thực hiện nhanh hơn. Điều này nói lên thực tế là mã bị chậm thậm chí một phút có thể được khuếch đại nếu mã đó đang được chạy hàng triệu lần. Mặc dù bản thân việc tra cứu từ điển có thể chỉ mất vài trăm nano giây, nhưng nếu chúng ta lặp lại hàng triệu lần trong quá trình tra cứu này, thì những nano giây đó có thể nhanh chóng tăng lên Nhược điểm - Từ điển và Bộ
Ghi chú. Sẽ thảo luận về việc thăm dò, hàm băm và thông đồng băm trong một blog khác, vì có rất nhiều điều cần đề cập dưới hàm băm Bộ hay từ điển nào nhanh hơn?So với danh sách và bộ, hiệu suất của từ điển tốt hơn , đặc biệt đối với các thao tác tìm kiếm, thêm và xóa. Một từ điển có thể được hoàn thành trong một độ phức tạp thời gian không đổi.
Được thiết lập nhanh hơn trong Python?Nói chung, danh sách nhanh hơn bộ. Nhưng trong trường hợp tìm kiếm một phần tử trong bộ sưu tập, bộ sẽ nhanh hơn vì bộ đã được triển khai bằng cách sử dụng bảng băm . Vì vậy, về cơ bản Python không phải tìm kiếm toàn bộ, điều đó có nghĩa là độ phức tạp thời gian trung bình là O(1).
dict() hay {} nhanh hơn?Như chúng ta có thể thấy, dict() rõ ràng là chậm hơn {} . Đặc biệt nếu dictionary được khởi tạo nhiều phần tử thì ảnh hưởng rất lớn nếu code của bạn cần 0. 04ms hoặc gần như 0. 08ms để tạo từ điển của bạn. Ngay cả khi bạn khởi tạo một từ điển trống, nó vẫn chậm hơn.
Bộ sưu tập nào nhanh hơn trong Python?Mảng NumPy nhanh hơn Danh sách Python vì những lý do sau. Mảng là một tập hợp các kiểu dữ liệu đồng nhất được lưu trữ trong các vị trí bộ nhớ liền kề. |