Bagaimana Set Bekerja Berbeda

Set: Dibangun untuk Pertanyaan Keanggotaan

Sebuah set menyimpan item unik menggunakan teknik yang disebut hashing. Ketika Anda menambahkan item, komputer menghitung hash (jejak jari numerik) yang menunjukkan persis di mana menyimpan item itu.

Ketika Anda memeriksa keanggotaan, komputer menghitung hash yang sama & melompat langsung ke tempat yang tepat. Tanpa pemindaian.

# A set of pets
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — duplicates removed
print(len(pets)) # 3 — only unique items

Perhatikan tiga perbedaan dari daftar:

1. Tidak ada duplikat. "cat" muncul dua kali dalam input tetapi set menyimpan hanya satu salinan.

2. Tidak ada urutan yang dijamin. Set mungkin mencetak item dalam pengaturan apa pun.

3. Tidak ada akses indeks. Anda tidak dapat menulis pets[0] — set tidak memiliki posisi.

Pertukaran: Anda kehilangan urutan & duplikat. Anda mendapatkan pengujian keanggotaan O(1) — memeriksa apakah item ada membutuhkan waktu yang sama apakah set memiliki 5 item atau 5 juta.

# Membership check — is "fish" in the set?
if "fish" in pets:    # hash("fish") → jump to bucket → found
    print("found!")   # checked exactly 1 spot, not 4

Keanggotaan Set vs Daftar

Anda memiliki 500 nama siswa yang disimpan dalam set daripada daftar.

students = {"Alex", "Maria", ..., "Zara", ...}  # 500 names
if "Zara" in students:
    print("enrolled")

Perbandingan Berdampingan

Lembar Tipuan Operasi

Gunakan daftar ketika Anda memerlukan:

- Item dalam urutan tertentu (playlist, resep, antrian)

- Akses berdasarkan posisi (items[3])

- Duplikat dipertahankan ("cat" muncul 3 kali = 3 kucing)

Gunakan set ketika Anda memerlukan:

- Pemeriksaan keanggotaan cepat ("apakah saya pernah melihat ini sebelumnya?")

- Penghapusan duplikat otomatis

- Tidak peduli dengan urutan

Gunakan keduanya ketika Anda memerlukan urutan DAN pencarian cepat:

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)

Pola "set + daftar" ini memberi Anda yang terbaik dari kedua: hasil yang terurut dengan deteksi duplikat yang cepat.

Pilih Struktur yang Tepat

Tiga masalah. Untuk setiap masalah, tentukan: daftar, set, atau keduanya?

1. Anda perlu menyimpan playlist lagu dalam urutan yang ditambahkan pengguna.

2. Anda perlu dengan cepat memeriksa apakah nama pengguna sudah diambil.

3. Anda perlu menghapus email duplikat dari mailing list tetapi mempertahankannya dalam urutan mereka mendaftar.

Masalah Deduplikasi

Masalah: Hapus Duplikat, Pertahankan Urutan

Anda menerima daftar pendaftaran email. Beberapa orang mendaftar dua kali. Anda perlu mengirim satu email per orang, dalam urutan mereka pertama kali mendaftar.

Upaya 1: hanya daftar (lambat)

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²)

Dengan 100 pendaftaran, ini melakukan ~5.000 pemeriksaan. Dengan 10.000 pendaftaran: ~50.000.000 pemeriksaan.

Upaya 2: set + daftar (cepat)

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)

Hasil yang sama. Urutan yang sama. Tetapi: 10.000 pendaftaran sekarang memerlukan ~10.000 pemeriksaan daripada ~50.000.000.

Hitung Peningkatan Kecepatan

Versi daftar-saja berjalan di O(N²). Versi set+daftar berjalan di O(N).

Anda memiliki 10.000 pendaftaran email untuk dideduplikasi.

Menemukan Elemen Umum

Masalah: Temukan Item di Kedua Daftar

Anda memiliki dua daftar kelas. Anda perlu menemukan siswa yang terdaftar di kedua kelas.

Pendekatan lambat: loop bersarang 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_b

Pendekatan cepat: ubah satu daftar ke set 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) each

Atau bahkan lebih sederhana menggunakan persimpangan set bawaan Python:

both = set(class_a) & set(class_b)  # O(N + M)

Operator & menemukan semua item yang muncul di kedua set.

Tulis Ulang untuk Kecepatan

Sebuah sekolah memiliki dua klub dengan 200 anggota masing-masing. Kode ini menemukan siswa di kedua klub:

chess_club = [...]   # 200 names
art_club = [...]     # 200 names
both_clubs = []
for student in chess_club:
    if student in art_club:
        both_clubs.append(student)

Kerangka Kerja Keputusan

Kerangka Kerja Keputusan Struktur Data Anda

Setiap kali Anda menulis kode yang menyimpan koleksi item, tanyakan:

1. Apakah saya memerlukan item dalam urutan? → daftar

2. Apakah saya memerlukan pemeriksaan keanggotaan cepat? → set

3. Apakah saya memerlukan keduanya urutan DAN pemeriksaan cepat? → set + daftar bersama

4. Apakah saya memerlukan duplikat? → daftar (set menghilangkan duplikat)

---

Wawasan kunci dari pelajaran ini: program yang sama, menyelesaikan masalah yang sama, dapat berjalan 1.000× hingga 1.000.000× lebih cepat hanya dengan memilih struktur data yang tepat. Tidak ada trik cerdas. Tidak ada matematika yang rumit. Hanya bertanya: operasi apa yang paling sering dilakukan kode saya? Kemudian pilih struktur di mana operasi tersebut biaya O(1) daripada O(N).

Pelajaran ini mencakup daftar & set. Struktur data lain ada (kamus, pohon, heap) yang menyelesaikan masalah lain. Kerangka kerja keputusan tetap sama: pahami operasi Anda, kemudian pilih struktur yang membuat mereka murah.

---

Ingin menggali lebih dalam? Pelajaran Big O kami mencakup tingkat pertumbuhan & perhitungan penskalaan secara detail. Lihat Big O: Seberapa Cepat Cukup Cepat?. Kursus unhamming kami mencakup cacat dunia nyata (MOAD-0001) di mana perbaikan daftar-ke-set yang tepat ini menghasilkan peningkatan kecepatan 1.000× dalam perangkat lunak produksi. Lihat Bab yang Hilang: Kompleksitas Algoritmik.

Debug Kode Ini

Seorang siswa menulis kode ini untuk menghitung berapa banyak kata unik yang muncul dalam sebuah buku:

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)

Buku memiliki 100.000 kata.