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 set được xác định bằng cách sử dụng hàm băm của đối tượng sẽ được thêm vào
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ụ
list. Hãy tưởng tượng bạn đang tìm chiếc bút của mình, nhưng bạn không biết chiếc bút của mình ở ngăn nào, vì vậy bạn phải lục từng ngăn cho đến khi tìm thấy [hoặc có thể bạn không bao giờ tìm thấy]. Đó là cái mà chúng tôi gọi là O[n], bởi vì trong trường hợp xấu nhất, bạn sẽ nhìn vào tất cả các ngăn kéo của mình [trong đó n là số ngăn kéo]
set. Bây giờ, hãy tưởng tượng bạn vẫn đang tìm bút của mình, nhưng bây giờ bạn biết bút của mình ở ngăn nào, chẳng hạn ở ngăn thứ 8. Vì vậy, bạn sẽ chỉ tìm kiếm trong ngăn kéo thứ 8, thay vì tìm kiếm trong tất cả các ngăn kéo. Đó là cái mà chúng tôi gọi là O[1], bởi vì trong trường hợp xấu nhất, bạn sẽ chỉ tìm trong một ngăn kéo
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,
- Nếu chúng ta đang thêm một phần tử — thì một tập hợp không cần di chuyển bất kỳ dữ liệu nào và tất cả những gì cần làm là tính giá trị băm và thêm nó vào bảng nhưng để chèn danh sách thì có khả năng sẽ có dữ liệu được di chuyển
- Nếu chúng tôi đang xóa một phần tử - tất cả những gì một bộ cần làm là xóa mục băm khỏi bảng băm, đối với một danh sách, nó có khả năng cần di chuyển dữ liệu xung quanh
- Nếu chúng ta đang tìm kiếm [i. e. một toán tử in] — một tập hợp chỉ cần tính giá trị băm của mục dữ liệu, tìm giá trị băm đó trong bảng băm và nếu nó ở đó — thì chơi lô tô. Đối với một danh sách, việc tìm kiếm phải tra cứu lần lượt từng mục. Ngay cả đối với nhiều 1000 mặt hàng, một bộ sẽ tìm kiếm nhanh hơn nhiều
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 Bapt
Loại có thể băm
Loạ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
- Lặp đi lặp lại tên của những người
- Tìm sự trùng khớp của tên bằng cách so sánh với các tên khác
- Tìm nạp số điện thoại tương ứng, sau khi tìm thấy kết quả trùng khớp
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]:
unique_names = []
for name, phonenumber in phonebook:
first_name, last_name = name.split[" ", 1]
for unique in unique_names:
if unique == first_name:
break
else:
unique_names.append[first_name]
return len[unique_names]- Chúng ta phải xem qua tất cả các mục trong danh bạ điện thoại và do đó vòng lặp này tốn O[n]
- Sau đó, chúng ta phải kiểm tra tên hiện tại với tất cả các tên duy nhất mà chúng ta đã thấy. Nếu đó là một tên duy nhất mới, chúng tôi sẽ thêm nó vào danh sách các tên duy nhất của chúng tôi. Sau đó, chúng tôi tiếp tục thông qua danh sách, thực hiện bước này cho mọi mục trong danh bạ điện thoại
Sử dụng phương pháp thiết lập
def set_unique_names[phonebook]:
unique_names = set[]
for name, phonenumber in phonebook:
first_name, last_name = name.split[" ", 1]
unique_names.add[first_name]
return len[unique_names]- Đối với phương thức set, thay vì lặp lại tất cả các tên duy nhất mà chúng ta đã thấy, chúng ta chỉ cần thêm tên hiện tại vào tập hợp các tên duy nhất. Vì các bộ đảm bảo tính duy nhất của các khóa mà chúng chứa, nên nếu chúng tôi cố gắng thêm một mục đã có trong bộ, thì mục đó sẽ không được thêm vào. Hơn nữa, chi phí hoạt động này O[1]
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]
1.13 s ± 26.8 ms per loop [mean ± std. dev. of 7 runs, 1 loop each]>>> %timeit set_unique_names[large_phonebook]
4.48 ms ± 177 µs per loop [mean ± std. dev. of 7 runs, 100 loops each]
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ó
Vì vậy, nếu chúng tôi đã phân bổ 8 khối bộ nhớ và giá trị băm của chúng tôi là 28975, thì chúng tôi coi bộ chứa ở chỉ mục 28975 & 0b111 = 7. Tuy nhiên, nếu từ điển đã phát triển để yêu cầu 512 khối bộ nhớ, mặt nạ sẽ trở thành 0b111111111 [và trong trường hợp này, chúng tôi sẽ xem xét nhóm ở chỉ mục 28975 & 0b11111111]. Bây giờ, nếu bộ chứa này khả dụng, thì chúng ta có thể lưu khóa và giá trị vào khối bộ nhớ. Nếu khối bộ nhớ không có sẵn, thì dict tìm khối bộ nhớ mới để chèn
Để tìm chỉ mục mới, Python sử dụng một cơ chế gọi là Probing
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ên
Khi 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
from math import sindef test1[x]:
"""
>>> %timeit test1[123_456]
162 µs ± 3.82 µs per loop [mean ± std. dev. of 7 runs, 10000 loops each]
"""
res = 1
for _ in range[1000]:
res += math.sin[x]
return resdef test2[x]:
"""
>>> %timeit test2[123_456]
124 µs ± 6.77 µs per loop [mean ± std. dev. of 7 runs, 10000 loops each]
"""
res = 1
for _ in range[1000]:
res += sin[x]
return resdef test3[x, sin=math.sin]:
"""
>>> %timeit test3[123_456]
105 µs ± 3.35 µs per loop [mean ± std. dev. of 7 runs, 10000 loops each]
"""
res = 1
for _ in range[1000]:
res += sin[x]
return res
Mã byte được tạo bằng mô-đun dis
Mã byte cho ba bài kiểm tra
Trong 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
Đây là một lý do khác để nói rõ ràng về những chức năng bạn đang nhập từ một mô-đun. Thực tiễn này không chỉ làm cho mã dễ đọc hơn, bởi vì trình đọc biết chính xác chức năng nào được yêu cầu từ các nguồn bên ngoài, mà nó còn đơn giản hóa việc thay đổi việc triển khai các chức năng cụ thể và nói chung là tăng tốc độ mã
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ộ
- Dung lượng bộ nhớ cao
- Hàm băm phức tạp dẫn đến tra cứu chậm hơn
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