Tại sao tìm kiếm trong từ điển nhanh hơn danh sách python?
|
Cả danh sách và từ điển đều được sử dụng để lưu trữ các bộ sưu tập dữ liệu. Từ điển < int, T > và Danh sách < T > tương tự nhau, cả hai đều là cấu trúc dữ liệu truy cập ngẫu nhiên của. Nền tảng NET. Từ điển dựa trên bảng băm, có nghĩa là nó sử dụng tra cứu hàm băm, đây là một thuật toán khá hiệu quả để tra cứu mọi thứ, mặt khác, một danh sách bạn phải đi từng phần tử cho đến khi tìm thấy kết quả từ đầu đến cuối Show
Khi so sánh với cấu trúc dữ liệu Danh sách, từ điển luôn có thời gian tra cứu ít nhiều cố định. Hãy đi cho một số chi tiết. Từ điển sử dụng hàm băm để tìm kiếm dữ liệu. Trước tiên, Từ điển tính giá trị băm cho khóa và giá trị băm này dẫn đến nhóm dữ liệu đích. Sau đó, mỗi phần tử trong thùng cần được kiểm tra sự bằng nhau. Nhưng thực ra danh sách sẽ nhanh hơn từ điển ở lần tìm kiếm đầu tiên vì không có gì để tìm kiếm trong bước đầu tiên. Nhưng ở bước thứ hai, danh sách phải xem qua mục đầu tiên rồi đến mục thứ hai. Vì vậy, mỗi bước tra cứu ngày càng mất nhiều thời gian hơn. Danh sách càng lớn thì càng mất nhiều thời gian. Tất nhiên, về nguyên tắc, Từ điển có khả năng tra cứu nhanh hơn với O(1) trong khi hiệu suất tra cứu của Danh sách là thao tác O(n) Từ điển ánh xạ một khóa tới một giá trị và không thể có các khóa trùng lặp, trong khi danh sách chỉ chứa một tập hợp các giá trị. Ngoài ra, Danh sách cho phép các mục trùng lặp và hỗ trợ truyền tải tuyến tính Xem xét ví dụ sau Thêm dữ liệu vào danh sách Cam danh sách chỉ cần thêm mục vào cuối mục danh sách hiện có Thêm dữ liệu vào từ điển Khi bạn thêm dữ liệu vào Từ điển, bạn nên chỉ định một khóa duy nhất cho dữ liệu để nó có thể được xác định duy nhất Từ điển có mã định danh duy nhất, vì vậy bất cứ khi nào bạn tra cứu một giá trị trong Từ điển, bộ thực thi phải tính toán mã băm từ khóa. Thuật toán được tối ưu hóa này được thực hiện bởi một số phép chia bit hoặc phép chia modulo ở mức độ thấp. Chúng tôi xác định thời điểm mà Từ điển trở nên hiệu quả hơn đối với việc tra cứu so với Danh sách Từ điển là gì? Lớp Từ điển cung cấp ánh xạ từ một tập hợp các khóa tới một tập hợp các giá trị. Từ điển được định nghĩa trong Hệ thống. bộ sưu tập. không gian tên chung. Mỗi bổ sung vào từ điển phải có một giá trị và khóa liên quan của nó. Nó cung cấp tra cứu nhanh để lấy giá trị từ các khóa của nó Làm cách nào để thêm các mục trong Từ điển? Lấy các mục từ từ điển thêm về. từ điển C# Danh sách là gì? Bên trong, List và ArrayList hoạt động bằng cách duy trì một mảng đối tượng bên trong, được thay thế bằng một mảng lớn hơn khi đạt dung lượng. Danh sách tự động thay đổi kích thước, vì vậy bạn không cần phải tự quản lý kích thước Làm cách nào để thêm các mục trong Danh sách? Làm cách nào để truy xuất các mục từ Danh sách? thêm về. Danh sách C# Từ điển Vs HashTableTừ điển là một loại chung, Hashtable thì không. Điều đó có nghĩa là bạn có được sự an toàn về kiểu với Từ điển, bởi vì bạn không thể chèn bất kỳ đối tượng ngẫu nhiên nào vào đó và bạn không phải bỏ các giá trị mà bạn lấy ra. Vì cả Từ điển và Hashtable đều là các bảng băm nội bộ, nên việc truy cập nhanh vào dữ liệu nhiều mục theo khóa, cả hai đều cần các khóa duy nhất và bất biến. thêm về. Từ điển Vs HashTable 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ộ. ” 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à 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 Tại sao tìm kiếm trong từ điển nhanh hơn danh sách?Lý do là vì từ điển là tra cứu, trong khi danh sách là phép lặp . Từ điển sử dụng tra cứu hàm băm, trong khi danh sách của bạn yêu cầu duyệt qua danh sách cho đến khi tìm thấy kết quả từ đầu đến kết quả mỗi lần.
Tại sao từ điển Python nhanh hơn danh sách?Danh sách là một tập hợp dữ liệu được sắp xếp theo thứ tự, trong khi các từ điển lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị bằng cách sử dụng cấu trúc hashtable. Do đó, việc tìm nạp các phần tử từ cấu trúc dữ liệu danh sách khá phức tạp so với từ điển trong Python . Do đó, từ điển nhanh hơn danh sách trong Python.
Việc lặp qua danh sách hoặc từ điển có nhanh hơn không?Khi có 10.000.000 mục tra cứu từ điển có thể nhanh hơn 585714 lần so với tra cứu danh sách . 6. 6 hoặc 585714 chỉ là kết quả chạy thử đơn giản với máy tính của tôi.
Tìm kiếm giá trị của từ điển trong Python có nhanh không?Lý do là từ điển rất nhanh , được triển khai bằng kỹ thuật gọi là băm, cho phép chúng tôi truy cập giá trị rất nhanh. Ngược lại, danh sách triển khai bộ dữ liệu chậm. Nếu chúng tôi muốn tìm một giá trị được liên kết với một khóa, chúng tôi sẽ phải lặp lại từng bộ dữ liệu, kiểm tra phần tử thứ 0. |
