Kümeler Nasıl Farklı Çalışır

Kümeler: Üyelik Soruları İçin İnşa Edilmiş

Bir küme hashing adlı bir teknik kullanarak benzersiz öğeleri depolar. Bir öğe eklediğinizde, bilgisayar o öğeyi tam olarak nerede saklamayı söyleyen bir hash (sayısal bir parmak izi) hesaplar.

Üyeliği kontrol ettiğinizde, bilgisayar aynı hash'i hesaplar & doğru noktaya doğrudan atlar. Tarama yapılmaz.

# Bir evcil hayvan seti
pets = {"cat", "dog", "cat", "fish", "dog"}

print(pets)      # {"cat", "dog", "fish"} — kopyalar kaldırılmış
print(len(pets)) # 3 — sadece benzersiz öğeler

Listelerden üç fark dikkat edin:

1. Yineleme yok. "cat" girdide iki kez göründü ancak küme yalnızca bir kopya tutar.

2. Garantili sıra yok. Küme öğeleri herhangi bir düzenlemede yazdırabilir.

3. Dizin erişimi yok. pets[0] yazamazsınız — kümelerin konumları yoktur.

Değiş tokuş: sırayı & yinelemeleri kaybedersiniz. O(1) üyelik testi kazanırsınız — bir öğenin var olup olmadığını kontrol etmek, kümenin 5 öğesi olsa da 5 milyon olsa da aynı zaman alır.

# Üyelik kontrolü — "fish" kümede mi?
if "fish" in pets:    # hash("fish") → kovaya atla → bulundu
    print("found!")   # tam 1 yeri kontrol etti, 4 değil

Küme vs Liste Üyeliği

Liste yerine kümede 500 öğrenci adınız var.

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

Yan Yana Karşılaştırma

İşlemler Referans Tablosu

Şu durumlarında listeyi kullanın:

- Öğeler belirli bir sırada (bir çalma listesi, bir tarif, bir kuyruk)

- Konuma göre erişim (items[3])

- Yinelenen öğeler korundu ("cat" 3 kez = 3 kedi)

Şu durumlarında kümeyi kullanın:

- Hızlı üyelik kontrolleri ("bunu daha önce gördüm mü?")

- Otomatik yineleme kaldırma

- Sıra konusunda endişe yok

Hem sıra hem de hızlı arama gerektiğinde her ikisini de kullanın:

seen = set()     # O(1) üyelik kontrolleri
result = []      # ekleme sırasını korur
for item in data:
    if item not in seen:  # O(1) kontrol
        seen.add(item)    # O(1) kümede ekle
        result.append(item)  # O(1) listeye ekle
# Toplam: O(N) — bir geçiş, her adım O(1)

Bu "küme + liste" deseni size her ikisinin en iyisini verir: hızlı yineleme algılaması ile sıralı sonuçlar.

Doğru Yapıyı Seç

Üç sorun. Her biri için karar verin: liste, küme, yoksa her ikisi de?

1. Kullanıcının eklediği sırada şarkıların bir çalma listesini depolamanız gerekiyor.

2. Bir kullanıcı adının zaten alınıp alınmadığını hızlı bir şekilde kontrol etmeniz gerekiyor.

3. Mailing listesinden yinelenen e-postaları kaldırmanız gerekiyor ancak bunları kaydolduğu sırada tutmanız gerekiyor.

Yinelemeleri Kaldırma Sorunu

Sorun: Yinelemeleri Kaldır, Sırayı Koru

Bir email kaydolma listesi alırsınız. Bazı kişiler iki kez kaydoldular. Her kişiye bir email göndermek gerekiyor, kaydolduğu sırada.

Girişim 1: sadece liste (yavaş)

signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
    if email not in unique:  # unique listesinin O(N) taraması
        unique.append(email)
# Çalışır! Ama: O(N) kontrol × N öğe = O(N²)

100 kayıt ile bu ~5.000 kontrol yapar. 10.000 kayıt ile: ~50.000.000 kontrol.

Girişim 2: küme + liste (hızlı)

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 araması
        seen.add(email)     # O(1) kümede ekle
        unique.append(email) # O(1) listeye ekle
# O(1) kontrol × N öğe = O(N)

Aynı sonuç. Aynı sıra. Ama: 10.000 kaydolma ~50.000.000 kontrol yerine ~10.000 kontrol gerektirir.

Hızlandırmayı Hesapla

Liste sürümü O(N²) hızında çalışır. Küme+liste sürümü O(N) hızında çalışır.

10.000 email kaydolmanız yinelenmesi gerekiyor.

Her İki Listede Ortak Öğeleri Bulma

Sorun: Her İki Listedeki Öğeleri Bulma

İki sınıf rosteriniz var. Her iki sınıfta da kayıtlı öğrencileri bulmanız gerekiyor.

Yavaş yaklaşım: iç içe döngüler O(N × M)

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a:        # N yineleme
    if student in class_b:     # her seferinde M tarama
        both.append(student)
# O(N × M) — her öğrenci class_b'nin tümüne karşı taranır

Hızlı yaklaşım: bir listeyi O(N + M) kümesine çevir

class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b)     # O(M) oluşturmak
both = []
for student in class_a:        # N yineleme
    if student in class_b_set: # her seferinde O(1)
        both.append(student)
# O(N + M) — kümeyi bir kez oluştur, N kez O(1) ile kontrol et

Veya Python'ın yerleşik küme kesişimini kullanan daha basit:

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

& operatörü her iki kümede görünen tüm öğeleri bulur.

Hızlı Olması İçin Yeniden Yazın

Bir okulun her biri 200 üyeli iki kulübü var. Bu kod her iki kulüpte bulunan öğrencileri bulur:

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

Karar Verme Çerçevesi

Veri Yapısı Karar Verme Çerçeveniz

Öğelerin bir koleksiyonunu depolayan her kod yazışında sorun:

1. Öğeleri sırada gerekiyor mu? → liste

2. Hızlı üyelik kontrollerine ihtiyacım var mı? → küme

3. Hem sıra hem de hızlı kontrol gerekiyor mu? → küme + liste birlikte

4. Kopyalara ihtiyacım var mı? → liste (kümeler kopyaları kaldırır)

---

Bu dersteki temel bilgi: aynı program, aynı sorunu çözerek, yalnızca doğru veri yapısını seçerek 1.000× ile 1.000.000× daha hızlı çalışabilir. Hiç akıllı numara. Hiç karmaşık matematik. Sadece sorma: kodum en sık hangi işlemleri yapar? Sonra işlemleri O(N) yerine O(1) maliyetinde yapan yapıyı seç.

Bu ders listeleri & kümeleri kapsamıştır. Diğer sorunları çözen başka veri yapıları vardır (sözlükler, ağaçlar, yığınlar). Karar çerçevesi aynı kalır: işlemlerinizi anlayın, sonra onları ucuz yapan yapıyı seçin.

---

Daha derinlemesine gitmek ister misiniz? Big O dersimiz büyüme oranlarını & ölçekleme hesaplamalarını ayrıntılı olarak kapsamıştır. Bkz Big O: Ne Kadar Hızlı Yeterince Hızlı?. Unhamming kursumuz bu tam liste-to-set düzeltmesi bir üretim yazılımında 1.000× hızlanma sağladığı gerçek düşün (MOAD-0001) içeriyor. Bkz Eksik Bölüm: Algoritmik Karmaşıklık.

Bu Kodu Ayıklayın

Bir öğrenci bir kitapta kaç benzersiz sözcüğün görülüp görülmediğini saymak için bu kodu yazdı:

words = book.split()           # tüm sözcükler listesi
unique_count = 0
checked = []
for word in words:             # N sözcük
    if word not in checked:    # checked listesini tara
        checked.append(word)
        unique_count += 1
print(unique_count)

Kitapta 100.000 sözcük var.