Bộ và từ điển có giống nhau trong Python không?

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

Nội dung chính Show

Loại có thể băm
Từ điển và Bộ — Sử dụng
đọc chính tả
Chèn và thay đổi kích thước
Từ điển & Không gian tên
Tra cứu không gian tên ví dụ
Nhược điểm - Từ điển và Bộ
Bộ từ điển có trong Python không?
Tập hợp có thể là khóa từ điển Python không?
Tại sao sử dụng một bộ thay vì một từ điển?
Bộ () trong Python là gì?

Ả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ố trí

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, 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

Bộ từ điển có trong Python không?

Lớp tập hợp của Python đại diện cho khái niệm toán học về tập hợp . Từ điển. trong Python là một đơn đặt hàng (kể từ Py 3. 7) [không có thứ tự (Py 3. 6 & trước)] tập hợp các giá trị dữ liệu, được sử dụng để lưu trữ các giá trị dữ liệu như bản đồ, không giống như các Loại Dữ liệu khác chỉ chứa một giá trị duy nhất dưới dạng phần tử, từ điển giữ khóa. cặp giá trị.

Tập hợp có thể là khóa từ điển Python không?

Tổng quan về Khóa và Giá trị trong Từ điển bằng Python . Các khóa trong từ điển là kiểu dữ liệu Boolean , integer , floating point number và string , tất cả đều được chấp nhận. Dictionary keys cannot be of a type that is mutable, such as sets , lists , or dictionaries . The keys in the dictionary are Boolean , integer , floating point number , and string data types, which are all acceptable.

Tại sao sử dụng một bộ thay vì một từ điển?

Một tập hợp và một từ điển về cơ bản là giống nhau, điểm khác biệt duy nhất là một tập hợp không có cặp khóa-giá trị và là một chuỗi các tổ hợp phần tử độc nhất và lộn xộn. We can also use the function get(key, default) . If the key does not exist, function get() returns a default value.