Những gì làm cho Danh sách Hữu ích
Danh sách: Cấu trúc Dữ liệu Đầu tiên của Bạn
Một danh sách (được gọi là mảng trong một số ngôn ngữ) lưu trữ các mục theo thứ tự cụ thể. Bạn có thể:
- Truy cập bất kỳ mục nào theo vị trí của nó: names[0] lấy mục đầu tiên. O(1) — tức thời.
- Thêm mục vào cuối: names.append("Zoe"). O(1) — tức thời.
- Duyệt qua từng mục theo thứ tự: for name in names. O(N) — truy cập mỗi mục một lần.
Danh sách bảo tồn thứ tự bạn đặt mọi thứ vào. Mục đầu tiên vẫn ở đầu. Mục cuối cùng vẫn ở cuối.
# A list of pets
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) instant
print(pets[3]) # "fish" — O(1) instant
print(len(pets)) # 5 — duplicates keptChú ý: "cat" xuất hiện hai lần. "dog" xuất hiện hai lần. Danh sách cho phép các mục trùng lặp. Chúng lưu trữ chính xác những gì bạn cung cấp, theo thứ tự bạn cung cấp.
Nhưng danh sách có một điểm yếu. Xem điều gì xảy ra khi bạn hỏi: có phải "fish" trong danh sách này không?
# Membership check — is "fish" in the list?
if "fish" in pets: # scans ["cat", "dog", "cat", "fish"...] one by one
print("found!") # had to check 4 items before finding itMáy tính kiểm tra "cat" — không. "dog" — không. "cat" — không. "fish" — có! Nó đã quét 4 mục để tìm được câu trả lời. Với 1.000 mục, nó có thể phải quét tất cả 1.000 mục. Kiểm tra thành viên này chi phí O(N).
Dự đoán Chi phí Quét
Bạn có một danh sách 500 tên học sinh theo thứ tự ngẫu nhiên.
Bạn muốn kiểm tra xem "Zara" có xuất hiện trong danh sách hay không.
students = ["Alex", "Maria", ..., "Zara", ...] # 500 names
if "Zara" in students:
print("enrolled")Cách Tập hợp Hoạt động Khác
Tập hợp: Được Xây dựng cho Câu hỏi Thành viên
Một tập hợp lưu trữ các mục duy nhất bằng cách sử dụng một kỹ thuật gọi là hashing. Khi bạn thêm một mục, máy tính tính toán một hàm băm (dấu vân tay số) cho bạn biết chính xác nơi lưu trữ mục đó.
Khi bạn kiểm tra thành viên, máy tính tính toán cùng một hàm băm & nhảy trực tiếp đến vị trí đúng. Không cần quét.
# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique itemsChú ý ba điểm khác biệt so với danh sách:
1. Không trùng lặp. "cat" xuất hiện hai lần ở đầu vào nhưng tập hợp chỉ giữ một bản sao.
2. Không có thứ tự được đảm bảo. Tập hợp có thể in các mục theo bất kỳ sắp xếp nào.
3. Không truy cập chỉ mục. Bạn không thể viết pets[0] — tập hợp không có vị trí.
Sự đánh đổi: bạn mất thứ tự & trùng lặp. Bạn lợi kiểm tra thành viên O(1) — kiểm tra xem một mục có tồn tại hay không mất cùng thời gian cho dù tập hợp có 5 mục hay 5 triệu.
# Membership check — is "fish" in the set?
if "fish" in pets: # hash("fish") → jump to bucket → found
print("found!") # checked exactly 1 spot, not 4Tập hợp so với Danh sách Thành viên
Bạn có 500 tên học sinh được lưu trữ trong một tập hợp thay vì danh sách.
students = {"Alex", "Maria", ..., "Zara", ...} # 500 names
if "Zara" in students:
print("enrolled")So sánh Kề nhau
Bảng Ghi nhớ Hoạt động
Sử dụng danh sách khi bạn cần:
- Các mục theo thứ tự cụ thể (một danh sách phát, một công thức nấu ăn, một hàng đợi)
- Truy cập theo vị trí (items[3])
- Trùng lặp được bảo tồn ("cat" xuất hiện 3 lần = 3 con mèo)
Sử dụng tập hợp khi bạn cần:
- Kiểm tra thành viên nhanh ("tôi đã thấy cái này trước đây chưa?")
- Tự động loại bỏ trùng lặp
- Không quan tâm đến thứ tự
Sử dụng cả hai khi bạn cần thứ tự VÀ tra cứu nhanh:
seen = set() # O(1) membership checks
result = [] # preserves insertion order
for item in data:
if item not in seen: # O(1) check
seen.add(item) # O(1) add
result.append(item) # O(1) append
# Total: O(N) — one pass, each step O(1)Mô hình "tập hợp + danh sách" này mang lại cho bạn điều tốt nhất của cả hai: kết quả theo thứ tự với phát hiện trùng lặp nhanh.
Chọn Cấu trúc Đúng
Ba vấn đề. Đối với mỗi vấn đề, quyết định: danh sách, tập hợp, hay cả hai?
1. Bạn cần lưu trữ một danh sách phát nhạc theo thứ tự mà người dùng thêm chúng.
2. Bạn cần kiểm tra nhanh xem tên người dùng đã được sử dụng chưa.
3. Bạn cần loại bỏ email trùng lặp từ danh sách gửi thư nhưng vẫn giữ chúng theo thứ tự họ đăng ký.
Vấn đề Loại bỏ Trùng lặp
Vấn đề: Loại bỏ Trùng lặp, Giữ Thứ tự
Bạn nhận được một danh sách đăng ký email. Một số người đã đăng ký hai lần. Bạn cần gửi một email cho mỗi người, theo thứ tự họ lần đầu tiên đăng ký.
Nỗ lực 1: chỉ danh sách (chậm)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
if email not in unique: # O(N) scan of unique list
unique.append(email)
# Works! But: O(N) check × N items = O(N²)Với 100 lần đăng ký, điều này thực hiện ~5.000 lần kiểm tra. Với 10.000 lần đăng ký: ~50.000.000 lần kiểm tra.
Nỗ lực 2: tập hợp + danh sách (nhanh)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
if email not in seen: # O(1) hash lookup
seen.add(email) # O(1) add to set
unique.append(email) # O(1) append to list
# O(1) check × N items = O(N)Kết quả giống nhau. Thứ tự giống nhau. Nhưng: 10.000 lần đăng ký bây giờ yêu cầu ~10.000 lần kiểm tra thay vì ~50.000.000.
Tính Tốc độ tăng
Phiên bản chỉ danh sách chạy ở O(N²). Phiên bản tập hợp+danh sách chạy ở O(N).
Bạn có 10.000 lần đăng ký email để loại bỏ trùng lặp.
Tìm Phần tử Chung
Vấn đề: Tìm Mục trong Cả hai Danh sách
Bạn có hai danh sách lớp. Bạn cần tìm học sinh ghi danh vào cả hai lớp.
Cách tiếp cận chậm: vòng lặp lồng nhau O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N iterations
if student in class_b: # M scans each time
both.append(student)
# O(N × M) — each student scanned against all of class_bCách tiếp cận nhanh: chuyển đổi một danh sách thành tập hợp O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) to build
both = []
for student in class_a: # N iterations
if student in class_b_set: # O(1) each time
both.append(student)
# O(N + M) — build the set once, check N times at O(1) eachHoặc thậm chí đơn giản hơn sử dụng giao điểm tập hợp tích hợp của Python:
both = set(class_a) & set(class_b) # O(N + M)Toán tử & tìm tất cả các mục xuất hiện trong cả hai tập hợp.
Viết lại để Tăng tốc độ
Một trường có hai câu lạc bộ mỗi câu có 200 thành viên. Mã này tìm học sinh trong cả hai câu lạc bộ:
chess_club = [...] # 200 names
art_club = [...] # 200 names
both_clubs = []
for student in chess_club:
if student in art_club:
both_clubs.append(student)Khung Quyết định
Khung Quyết định Cấu trúc Dữ liệu của Bạn
Mỗi khi bạn viết mã lưu trữ một tập hợp các mục, hãy hỏi:
1. Tôi có cần các mục theo thứ tự không? → danh sách
2. Tôi có cần kiểm tra thành viên nhanh không? → tập hợp
3. Tôi có cần cả thứ tự VÀ kiểm tra nhanh không? → tập hợp + danh sách cùng nhau
4. Tôi có cần trùng lặp không? → danh sách (các tập hợp loại bỏ trùng lặp)
---
Cái nhìn sâu sắc chính từ bài học này: cùng một chương trình, giải quyết cùng một vấn đề, có thể chạy 1.000× đến 1.000.000× nhanh hơn chỉ bằng cách chọn cấu trúc dữ liệu phù hợp. Không có mẹo lclever. Không có toán học phức tạp. Chỉ hỏi: hoạt động nào mà mã của tôi thực hiện thường xuyên nhất? Sau đó chọn cấu trúc mà những hoạt động đó chi phí O(1) thay vì O(N).
Bài học này bao gồm danh sách & tập hợp. Các cấu trúc dữ liệu khác tồn tại (từ điển, cây, heap) giải quyết các vấn đề khác. Khung quyết định vẫn giữ nguyên: hiểu các hoạt động của bạn, sau đó chọn cấu trúc làm cho chúng rẻ.
---
Muốn đi sâu hơn? Bài học Big O của chúng tôi bao gồm chi tiết về tốc độ tăng & tính toán tỷ lệ. Xem Big O: Cái gì Đủ Nhanh?. Khóa học unhamming của chúng tôi bao gồm lỗi thực tế (MOAD-0001) nơi việc sửa chữa danh sách-thành-tập hợp chính xác này tạo ra tốc độ tăng 1.000× trong phần mềm sản xuất. Xem Chương Thiếu: Độ phức tạp Thuật toán.
Gỡ lỗi Mã này
Một học sinh đã viết mã này để đếm bao nhiêu từ duy nhất xuất hiện trong một cuốn sách:
words = book.split() # list of all words
unique_count = 0
checked = []
for word in words: # N words
if word not in checked: # scans checked list
checked.append(word)
unique_count += 1
print(unique_count)Cuốn sách có 100.000 từ.