Kümeler ve Çok Kümeler

Karma tablosu bir anahtarı bir değere eşler. Bazı problemlerde değer yoktur; sorulan tek soru “bu eleman var mı” olur. Yinelenenlerin ayıklanması, bir kimliğin listede olup olmadığının sınanması, iki koleksiyonun ortak elemanlarının bulunması bu sınıftandır.

Küme (set), üyelik odaklı soyut veri tipidir: her eleman ya vardır ya yoktur, sayısı tutulmaz, sırası tanımlı değildir.

Küme İşlemleri

İşlem	Anlamı
ekle	Elemanı kümeye katar; zaten varsa değişiklik olmaz
sil	Elemanı çıkarır
iceriyor_mu	Üyelik sınaması
birlesim	İki kümenin tüm elemanları
kesisim	İkisinde birden bulunanlar
fark	Birincide olup ikincide olmayanlar
alt_kume_mu	Kapsama sınaması

İlk üçü tekil elemanla, son dördü küme çiftiyle çalışır. Maliyetleri farklı düşünülür: tekil işlemler eleman sayısından bağımsız olabilirken, küme işlemleri en az bir kümeyi gezmek zorundadır.

Gerçekleştirim Seçenekleri

Karma kümesi, değeri olmayan bir karma tablosudur. Tekil işlemler ortalama sabit zamanlıdır; sıra korunmaz.

Sıralı küme, elemanları sıralı tutan bir yapıyla (dengeli ağaç veya atlama listesi) kurulur. Tekil işlemler logaritmiktir; karşılığında elemanlar sıralı gezilebilir ve aralık sorgusu yapılabilir — “değeri 10 ile 20 arasında olanlar” gibi.

Seçim ölçütü nettir: sıra veya aralık gerekmiyorsa karma kümesi, gerekiyorsa sıralı küme.

Bit Kümesi

Elemanlar $0$ ile $N-1$ arasındaki tam sayılarsa ve $N$ makul büyüklükteyse, üçüncü ve çok daha verimli bir gerçekleştirim vardır: her eleman için tek bir bit.

Bit kümesi (bitset), üyeliği bit düzeyinde tutar. Bilgisayarlar Nasıl Çalışır kursundaki bit düzeyi işlemler burada doğrudan kullanılır.

class BitKumesi:
    """0..N-1 aralığındaki tam sayıları bit düzeyinde tutar."""

    def __init__(self, evren: int) -> None:
        self.evren = evren
        self._bitler = 0                       # tek bir büyük tam sayı

    def ekle(self, deger: int) -> None:
        self._bitler |= 1 << deger             # ilgili biti kur

    def sil(self, deger: int) -> None:
        self._bitler &= ~(1 << deger)          # ilgili biti sıfırla

    def iceriyor_mu(self, deger: int) -> bool:
        return ((self._bitler >> deger) & 1) == 1

    def birlesim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler | digeri._bitler
        return sonuc

    def kesisim(self, digeri: "BitKumesi") -> "BitKumesi":
        sonuc = BitKumesi(self.evren)
        sonuc._bitler = self._bitler & digeri._bitler
        return sonuc

    def elemanlar(self) -> list[int]:
        return [i for i in range(self.evren) if self.iceriyor_mu(i)]

    def __len__(self) -> int:
        return bin(self._bitler).count("1")    # kurulu bit sayısı


a = BitKumesi(16)
b = BitKumesi(16)
for d in (1, 3, 5, 7):
    a.ekle(d)
for d in (3, 5, 9):
    b.ekle(d)

print(a.elemanlar(), b.elemanlar())            # [1, 3, 5, 7] [3, 5, 9]
print(a.kesisim(b).elemanlar())                # [3, 5]
print(a.birlesim(b).elemanlar())               # [1, 3, 5, 7, 9]
print(len(a), a.iceriyor_mu(7), a.iceriyor_mu(8))   # 4 True False

İki üstünlüğü vardır ve ikisi de büyüktür.

Bellek. Eleman başına bir bit kullanılır. Bir milyon elemanlık evren, 125 kilobayta sığar; aynı kümeyi karma kümesiyle tutmak, eleman başına onlarca bayt ister.

Küme işlemleri sözcük düzeyinde paraleldir. İki bit kümesinin kesişimi, tek bir VE işlemidir; işlemci 64 elemanı tek komutta işler. Karma kümesinde aynı işlem, elemanların tek tek gezilmesini gerektirir.

Koşulu ise dardır: evren küçük ve yoğun olmalıdır. Elemanlar milyarlar arasında dağınık birkaç değerse, bit kümesi bellek israfına döner. Bu durumda seyrek gösterimler veya karma kümesi tercih edilir.

Bit kümeleri, veritabanı dizinlerinde satır kümelerini birleştirmek, çizge algoritmalarında ziyaret edilmiş düğümleri işaretlemek ve izin kümelerini tutmak için yaygın kullanılır.

Çok Küme

Küme, bir elemanın var olup olmadığını söyler; kaç kez var olduğunu söylemez. Sayı gerektiğinde çok küme (multiset) kullanılır: her elemanla birlikte bir sayaç tutulur.

def frekans(olcumler: list[int]) -> dict[int, int]:
    """Her değerin kaç kez geçtiğini sayar."""
    sayac: dict[int, int] = {}
    for olcum in olcumler:
        sayac[olcum] = sayac.get(olcum, 0) + 1
    return sayac


olcumler = [12, 18, 7, 12, 25, 12, 18]
print(frekans(olcumler))                       # {12: 3, 18: 2, 7: 1, 25: 1}
print(max(frekans(olcumler).items(), key=lambda c: c[1]))   # (12, 3)

Çok küme, aslında değeri sayı olan bir eşlemedir; ayrı bir yapı olarak anılmasının nedeni, küme işlemlerinin sayaçlarla tanımlanmasıdır: birleşimde sayaçların en büyüğü, kesişimde en küçüğü alınır.

Tipik kullanımı sayım problemleridir: sözcük frekansları, en sık geçen değerler, örneklem dağılımları. Veri analitiği müfredatındaki frekans çözümlemeleri bu yapının üzerine kurulur.

Küme mi Liste mi

Yaygın bir başarım hatası, üyelik sınamasının liste üzerinde yapılmasıdır. Liste araması doğrusaldır; aynı sınama küme üzerinde ortalama sabittir.

kimlikler = list(range(100_000))
kume = set(kimlikler)

# Liste üzerinde üyelik: her sorgu tüm listeyi tarayabilir.
print(99_999 in kimlikler)      # True — en kötü durumda 100.000 karşılaştırma
# Küme üzerinde üyelik: karma ile tek adım.
print(99_999 in kume)           # True — kova hesabı ve birkaç karşılaştırma

Fark, sınama sayısıyla çarpılır: bir liste içinde $m$ sorgu yapmak $O(n \cdot m)$, kümede $O(m)$’dir. Bir döngü içinde yapılan üyelik sınaması bu nedenle standart bir gözden geçirme noktasıdır.

Kümeye dönüştürmenin de bir maliyeti vardır — tüm elemanların eklenmesi $O(n)$. Tek bir sorgu için dönüştürmek anlamsızdır; sorgu sayısı arttıkça dönüşüm kendini öder.

Küme İşlemlerinin Maliyeti

İki kümenin kesişimi hesaplanırken küçük kümenin gezilip büyük kümede üyelik sınanması, tersinden yapmaktan ucuzdur:

$$O(\min(\lvert A\rvert, \lvert B\rvert)) \quad \text{yerine} \quad O(\lvert A\rvert)$$

Bu ayrıntı, büyük veri kümeleriyle çalışırken belirgin fark yaratır ve kütüphane gerçekleştirimlerinin çoğu bunu kendiliğinden yapar.

Sıralı kümelerde ise farklı bir yol vardır: iki sıralı diziyi birleştirir gibi tek geçişte ilerlemek, $O(\lvert A\rvert + \lvert B\rvert)$ maliyetle tüm küme işlemlerini verir ve ek bellek gerektirmez.

Maliyet Tablosu

Yapı	Üyelik	Ekleme	Kesişim	Sıra
Karma kümesi	$O(1)$ ortalama	$O(1)$ ortalama	$O(\min(\lvert A\rvert, \lvert B\rvert))$	Yok
Sıralı küme	$O(\log n)$	$O(\log n)$	$O(\lvert A\rvert + \lvert B\rvert)$	Var
Bit kümesi	$O(1)$	$O(1)$	$O(N / w)$*	Değere göre

* $w$, işlemcinin sözcük genişliği; $N$ evren büyüklüğü.

Özet

• Küme, üyelik odaklı soyut tiptir; eleman ya vardır ya yoktur, sayısı ve sırası tutulmaz.
• Karma kümesi tekil işlemleri ortalama sabit zamanda yapar ama sıra korumaz; sıralı küme logaritmik maliyetle sıra ve aralık sorgusu sağlar.
• Bit kümesi, küçük ve yoğun tam sayı evrenlerinde eleman başına tek bit kullanır ve küme işlemlerini sözcük düzeyinde paralel yapar.
• Çok küme, elemanla birlikte sayaç tutar; sayım problemlerinin doğal yapısıdır.
• İki küme kesiştirilirken küçük olanın gezilmesi, maliyeti küçük kümenin boyutuna indirir.

Sonraki Adım

Buraya kadar kümeler bağımsız düşünüldü. Bazı problemlerde ise sorulan soru farklıdır: “bu iki eleman aynı grupta mı?” ve gruplar zamanla birleşiyor. Sonraki ders, bu soruyu neredeyse sabit zamanda yanıtlayan ayrık küme yapısını ele alacak.