Bagaimana Set Bekerja Bedanya

Set: Dirancang untuk Pertanyaan Keanggotaan

Sebuah set menyimpan item unik menggunakan teknik yang disebut hashing. Saat Anda menambahkan item, komputer menghitung hash (jari-jari numerik) yang memberitahu komputer secara persis di mana item tersebut harus disimpan.

Saat Anda memeriksa keanggotaan, komputer menghitung hash yang sama & langsung berpindah ke spot yang tepat. Tidak ada scanning.

# Sebuah set hewan peliharaan
hewan = {"kucing", "anak anjing", "kucing", "ikan", "anak anjing"}

print(hewan) # {"kucing", "anak anjing", "ikan"} — duplikat dihapus
print(len(hewan)) # 3 — hanya item unik

Perhatikan tiga perbedaan dari daftar:

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

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

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

Tukar menukar: Anda kehilangan urutan & duplikat. Anda mendapatkan O(1) testing keanggotaan — memeriksa apakah item ada dalam set menghabiskan waktu yang sama, baik set memiliki 5 item atau 5 juta.

# Pengecekan keanggotaan — apakah "ikan" ada dalam set?
if "ikan" in hewan: # hash("ikan") → pindah ke bucket → ditemukan
    print("ditemukan!") # diperiksa tepatnya 1 tempat, bukan 4

Set vs Daftar Keanggotaan

Anda memiliki 500 nama siswa yang disimpan dalam sebuah set alih-alih dalam daftar.

siswa = {"Alex", "Maria", ..., "Zara", ...}  # 500 nama
jika "Zara" ada di siswa:
    cetak("terdaftar")

Perbandingan Sisi-Sisi

Cheat Sheet Operasi

Gunakan daftar jika Anda membutuhkan:

- Item dalam urutan tertentu (daftar putar, resep, antrian)

- Akses berdasarkan posisi (items[3])

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

Gunakan set jika Anda membutuhkan:

- Cek keanggotaan cepat ("sudah saya lihat sebelumnya?")

- Penghapusan otomatis duplikat

- Tidak peduli urutan

Gunakan keduanya jika Anda membutuhkan urutan DAN pencarian cepat:

seen = set()     # O(1) cek keanggotaan
result = []      # mempertahankan urutan pengaturan
for item in data:
    if item not in seen:  # O(1) periksa
        seen.add(item)    # O(1) tambahkan
        result.append(item)  # O(1) tambahkan
# Total: O(N) — satu kali lewati, setiap langkah O(1)

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

Pilih Struktur yang Tepat

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

1. Anda perlu menampung daftar lagu-lagu dalam urutan di mana pengguna menambahkannya.

2. Anda perlu dengan cepat mengecek apakah username telah digunakan sebelumnya.

3. Anda perlu menghapus email yang duplikat dari daftar mailing tetapi tetap mempertahankan urutan mereka saat mendaftar.

Masalah Pengurangan Duplikat

Masalah: Hapus Duplikat, Pertahankan Urutan

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

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)
# Berhasil! Tapi: O(N) cek × N item = 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) cek × N item = O(N)

Hasil yang sama. Urutan yang sama. Tapi: 10.000 pendaftaran sekarang membutuhkan ~10.000 pemeriksaan daripada ~50.000.000.

Hitung Kecepatan Peningkatan

Versi hanya daftar berjalan pada O(N²). Versi set+list berjalan pada O(N).

Anda memiliki 10,000 pendaftaran email untuk dihapus duplikat.

Mencari Element Umum

Masalah: Temukan Item dalam Kedua Daftar

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

Pendekatan lambat: nested loops O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N iterasi
    if student in class_b:     # M scan setiap kali
        both.append(student)
# O(N × M) — setiap siswa di-scan terhadap semua class_b

Pendekatan cepat: ubah satu daftar menjadi set O(N + M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) untuk membuatnya
both = []
for student in class_a:        # N iterasi
    if student in class_b_set: # O(1) setiap kali
        both.append(student)
# O(N + M) — buat set sekali, periksa N kali pada O(1) setiap kali

Atau bahkan lebih sederhana menggunakan set intersection built-in Python:

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

Operator & mencari semua item yang muncul dalam kedua set.

Tulis Kembali untuk Kebutuhan 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 Keputusan Data Struktur

Kerangka Keputusan Data Struktur Anda

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

1. Apakah saya membutuhkan item dalam urutan? → list

2. Apakah saya membutuhkan pemeriksaan keanggotaan cepat? → set

3. Apakah saya membutuhkan urutan dan pemeriksaan cepat? → set + list bersama

4. Apakah saya membutuhkan duplikat? → list (set menghilangkan duplikat)

---

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

Les ini membahas tentang daftar & himpunan. Struktur data lainnya ada (kamus, pohon, heep) yang mengatasi masalah yang berbeda. Framework keputusan tetap sama: **pahami operasi Anda, kemudian pilih struktur yang membuatnya murah.

---

Ingin menggali lebih dalam? Les Big O kami membahas tentang laju pertumbuhan & perhitungan skalabilitas secara rinci. Lihat [Big O: Berapa cepat cukup?](/en/nu/cs_algorithms_big_o_notation). Les unhamming kami membahas tentang kecacatan nyata (MOAD-0001) di mana perbaikan ini dari daftar ke himpunan menghasilkan percepatan kecepatan 1.000× pada perangkat lunak produksi. Lihat [Bab yang Hilang: Kompleksitas Algoritma](/en/un/unhamming_algorithmic_complexity).

Debug This Code

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

words = book.split()           # daftar semua kata
unique_count = 0
checked = []
for word in words:             # N kata
    if word not in checked:    # memeriksa daftar checked
        checked.append(word)
        unique_count += 1
print(unique_count)

Buku tersebut memiliki 100.000 kata.