Tại sao đặt tìm kiếm nhanh hơn danh sách trong Python?

Trong Python, có bốn kiểu dữ liệu tích hợp mà chúng ta có thể sử dụng để lưu trữ các bộ sưu tập dữ liệu. Với những phẩm chất và đặc điểm khác nhau, các kiểu dữ liệu dựng sẵn này là List (danh sách), Tuple (tuple), Set (bộ) và Dictionary (dict)

Trong bài viết này, chúng ta sẽ tìm hiểu sâu về List, Tuple và Set trong Python. Chúng tôi sẽ xem xét sự khác biệt của chúng và khi nào nên sử dụng các loại dữ liệu này

Vì Từ điển liên kết các khóa với các giá trị tương ứng của chúng, đây là trường hợp sử dụng rất khác so với Danh sách, Bộ và Tập hợp (chỉ đơn giản là chứa các giá trị), nó sẽ không nằm trong cuộc thảo luận này

Để đơn giản, tôi sẽ sử dụng Set và Dictionary thay thế cho nhau, vì chúng dựa trên Hash Table (hoặc Hash Map)

Tại sao chúng ta quan tâm?

Phần lớn, các kiểu dữ liệu này có thể được sử dụng thay thế cho nhau trong một ứng dụng mà không gặp nhiều rắc rối

Tuy nhiên, hãy tưởng tượng nếu chúng ta được giao nhiệm vụ kiểm tra xem có một cây kim nào tồn tại trong một đống cỏ khô lớn không. Điều gì sẽ là cách hiệu quả nhất về tốc độ và bộ nhớ để làm như vậy?

Haystack có nên là một Danh sách không?

Nào cùng đào vào bên trong

Sự khác biệt giữa Danh sách, Tuple và Set

trùng lặp

Nếu tôi giải thích điều này, List và Tuple giống như anh em ruột trong Python. Mặt khác, Bộ (hoặc Từ điển) giống như anh em họ của cả hai

Không giống như Danh sách hoặc Tuple, Tập hợp không thể chứa các bản sao. Nói cách khác, các phần tử trong Set là duy nhất

set_example = {1, 1, 2, 3, 3, 3}
# {1, 2, 3}

fruit_set = {'🍎', '🍓', '🍐', '🍎', '🍎', '🍓'}
# {'🍎', '🍐', '🍓'}

Với kiến ​​thức này, giờ đây chúng ta biết rằng Set cũng có thể được sử dụng để xóa các mục trùng lặp khỏi danh sách

Gọi món

Bạn có thể đã nghe tuyên bố “Bộ và Từ điển không được sắp xếp theo thứ tự trong Python. ” Chà, đó chỉ là một nửa sự thật ngày nay, tùy thuộc vào phiên bản Python bạn đang sử dụng

Trước Python 3. 6, Từ điển và Bộ không giữ thứ tự chèn của chúng. Đây là một ví dụ nếu bạn dùng thử trong Python 3. 5

# Example in Python 3.5

fruit_size = {} 
>>> fruit_size['🍎'] = 12 
>>> fruit_size['🍐'] = 16 
>>> fruit_size['🍇'] = 20 
>>> fruit_size
{'🍎': 12, '🍇': 20, '🍐': 16}

Bạn có thể dễ dàng chuyển sang các phiên bản Python khác nhau bằng pyenv. dùng thử

Hôm nay, tuyên bố đó đã lỗi thời trong một vài năm. Bắt đầu từ Python 3. 7, Từ điển và Bộ được sắp xếp chính thức theo thời điểm chèn

Dù sao, trong trường hợp bạn thắc mắc, Danh sách và Tuple là các chuỗi đối tượng được sắp xếp theo thứ tự

khả năng biến đổi

Khi bạn mô tả một đối tượng là có thể thay đổi, đó chỉ đơn giản là một cách thú vị để nói trạng thái bên trong của đối tượng có thể thay đổi

Sự khác biệt chính ở đây là Tuple là bất biến (không thể thay đổi), trong khi Danh sách và Tập hợp có thể thay đổi

Mặc dù Bộ có thể thay đổi, nhưng chúng tôi không thể truy cập hoặc thay đổi bất kỳ phần tử nào của Bộ thông qua lập chỉ mục hoặc cắt. Do đó, chúng ta chỉ có thể thêm các phần tử mới vào một tập hợp — không thể thay đổi chúng

Xin lưu ý rằng phương thức cập nhật trong Tập hợp chỉ đơn giản có nghĩa là khả năng thêm nhiều phần tử cùng một lúc

lập chỉ mục

Cả Tuple và List đều hỗ trợ lập chỉ mục và cắt, trong khi Set thì không

fruit_list = ['🍎', '🍓', '🍐']
fruit_list[1]
# '🍓'

animal_tuple = ('🐶', '🐱', '🐮')
animal_tuple[2]
# '🐮'

vehicle_set = {'🚐', '🏍', '🚗'}
vehicle_set[0]
# TypeError: 'set' object is not subscriptable

Khi nào nên sử dụng Danh sách so với. Tuple?

Như chúng tôi đã đề cập trước đó, Bộ dữ liệu là bất biến, trong khi Danh sách có thể thay đổi. Tương tự như vậy, Tuples có kích thước cố định về bản chất, trong khi Lists là động

a_tuple = tuple(range(1000))
a_list = list(range(1000))
a_tuple.__sizeof__()  # 8024 bytes
a_list.__sizeof__()   # 9088 bytes

Sử dụng danh sách

1. Khi bạn cần thay đổi bộ sưu tập của mình
2. Khi bạn cần xóa hoặc thêm mục mới vào bộ sưu tập mục của mình

Sử dụng Tuple

1. Nếu dữ liệu của bạn nên hoặc không cần phải thay đổi
2. Bộ dữ liệu nhanh hơn danh sách. Chúng ta nên sử dụng Tuple thay vì Danh sách nếu chúng ta đang xác định một tập giá trị không đổi và tất cả những gì chúng ta sẽ làm với nó là lặp qua nó
3. Nếu chúng ta cần một mảng các phần tử được sử dụng làm khóa từ điển, chúng ta có thể sử dụng Tuples. Vì Danh sách có thể thay đổi (loại không thể xóa), chúng không bao giờ có thể được sử dụng làm khóa từ điển

Khi nào nên sử dụng Set so với. Danh sách/Tuple?

Vì Set sử dụng Bảng băm làm cấu trúc dữ liệu cơ bản nên Set rất nhanh khi kiểm tra xem một phần tử có nằm trong nó không (e. g. x in a_set)

Ý tưởng đằng sau nó là việc tra cứu một mục trong bảng băm là thao tác O(1) (thời gian không đổi)

"Vậy, tôi nên luôn sử dụng Bộ hay Từ điển?"

Về cơ bản, nếu bạn không cần lưu trữ các bản sao, Set sẽ tốt hơn List. Giai đoạn = Stage

Tóm lược

Các bài học chính là gì?

• Nếu bạn cần lưu trữ các bản sao, hãy truy cập Danh sách hoặc Tuple
• Đối với danh sách vs. Tuple, nếu bạn không có ý định đột biến, hãy tìm Tuple
• Nếu bạn không cần lưu trữ các bản sao, hãy luôn truy cập Đặt hoặc Từ điển. Bản đồ băm nhanh hơn đáng kể khi xác định xem một đối tượng có mặt trong Tập hợp hay không (e. g. x trong set_or_dict)

Nếu bạn là một người đam mê số như tôi, hãy xem điều này khi bạn đang lặp lại hoặc kiểm tra xem một đối tượng có mặt trong một bộ sưu tập hay không

Tại sao được thiết lập nhanh hơn nhiều so với danh sách?

Bộ tra cứu có nhanh hơn danh sách Python không?

Tại sao set tốt hơn list trong Python?

Việc lặp qua một tập hợp có nhanh hơn một danh sách không?