Kümeler

Önceki dersin ölçümünde küme, sözlüğün yanında sessizce durdu ve aynı sayıları verdi: bulunan öğede 1, bulunmayan öğede 0 karşılaştırma. Kendi başına ne yaptığı sorulmadı.

Küme (set), yalnız üyelik tutan kaptır — değeri yoktur, sırası yoktur, tekrarı yoktur. Bu üç yokluk aynı düzeneğin sonucudur ve bu dersin ölçtüğü işi doğrudan mümkün kılar: bir veri yığınındaki tekrarları atmak. Soru yine sayıyla yanıtlanacak. Tekrarları elle ayıklamak ile kümeye vermek kaç karşılaştırmaya mal oluyor, ve geri dönen kapta öğeler yeni mi, eski mi?

Kümenin Sorusu

Küme bir öğeyi tutarken “kaçıncı sırada” diye sormaz; yalnız “bu zaten var mı” diye sorar. Yanıtı, önceki derste sözlüğün anahtar için kullandığı yolla bulur: öğenin karma değerinden hangi bölmeye düştüğünü hesaplar ve orada bakar. Bu yüzden kümenin öğeleri de karmalanabilir olmak zorundadır; demetler dersinde ölçülen koşulun aynısı burada öğeler için geçerlidir.

Bu düzeneğin kendisi — karma tablosu, çakışma, yük çarpanı — Veri Yapıları kursunda kuruldu ve tekrarlanmaz. Burada ölçülen şey, aynı işin iki yazımının kaç somut karşılaştırmaya mal olduğudur; büyüme sınıfı iddiası değildir, belirli bir veriyle yapılmış bir sayımdır. Karşılaştırmaları öğenin kendisi sayar.

Tekilleştirmenin elle yazımı doğrudan ve okunaklıdır: sonuç listesi tutulur, her öğe için “bu listede var mı” diye bakılır, yoksa eklenir. Bu yazımın gizli maliyeti, “var mı” sorusunun her seferinde bir listeye sorulmasıdır — ve önceki ders bir listeye sorulan üyelik sorusunun neye mal olduğunu ölçmüştü.

• KL40 — Ham veri üç yüz öğedir ve yüz ayrı değer taşır; her değer tam üç kez geçer. Beklenen sonuç bu yüzden önceden bilinir ve kâhin kurgudur.
• KL41 — Üç yöntem de aynı ham listeyle çalışır; öğeler bir kez var edilir ve yöntemlerin hiçbiri yeni öğe kurmaz.
• KL42 — Sayaç her yöntemden hemen önce sıfırlanır; ham verinin kurulması ölçüme girmez.
• KL43 — “Yeni öğe” sütunu, sonuçtaki her öğenin ham veride is ile aranmasıyla bulunur; sıfır olması sonucun paylaşıldığı anlamına gelir.
• KL44 — Sıra sütunu yalnız sıra güvencesi olan yöntemler için doldurulur; kümenin öğelerini hangi düzende verdiği ölçülmez ve ona dayanılmaz.

"""Tekillestirme: uc yontem, ayni sonuc, ayri sayida karsilastirma."""


class Sayan:
    """Esitlik karsilastirmalarini sayan deger."""

    sayac = {"karsilastirma": 0}

    def __init__(self, d):
        self.d = d

    def __eq__(self, o):
        Sayan.sayac["karsilastirma"] += 1
        return isinstance(o, Sayan) and self.d == o.d

    def __hash__(self):
        return hash(self.d)


BENZERSIZ = 100
HAM = [Sayan(i % BENZERSIZ) for i in range(3 * BENZERSIZ)]


def elle(ham):
    sonuc = []
    for x in ham:
        if x not in sonuc:
            sonuc.append(x)
    return sonuc


def kumeye_ver(ham):
    return set(ham)


def anahtar_yap(ham):
    return dict.fromkeys(ham)


print(f"{'yöntem':<22s}{'karşılaştırma':>14s}{'benzersiz':>10s}"
      f"{'yeni öğe':>9s}{'sıra korunur':>14s}")
ILK = None
for ad, yontem, sirali in (("elle tarama", elle, True),
                           ("set(ham)", kumeye_ver, False),
                           ("dict.fromkeys(ham)", anahtar_yap, True)):
    Sayan.sayac["karsilastirma"] = 0
    sonuc = yontem(HAM)
    sayi = Sayan.sayac["karsilastirma"]
    yeni = sum(1 for x in sonuc if not any(x is y for y in HAM))
    if ILK is None:
        ILK = list(sonuc)
    ayni_sira = list(sonuc) == ILK
    print(f"{ad:<22s}{sayi:>14d}{len(sonuc):>10d}{yeni:>9d}"
          f"{str(ayni_sira) if sirali else 'güvence yok':>14s}")

print()
print(f"ham veri {len(HAM)} öğe | tekrar {len(HAM) - BENZERSIZ} | "
      f"benzersiz {BENZERSIZ}")
print(f"elle taramanın sonucundaki öğeler ham veriden mi: "
      f"{all(any(x is y for y in HAM) for x in elle(HAM))}")

yöntem                 karşılaştırma benzersiz yeni öğe  sıra korunur
elle tarama                    15050       100        0          True
set(ham)                         200       100        0   güvence yok
dict.fromkeys(ham)               200       100        0          True

ham veri 300 öğe | tekrar 200 | benzersiz 100
elle taramanın sonucundaki öğeler ham veriden mi: True

Aynı Yüz Öğe, Üç Ayrı Fatura

Üç satırın “benzersiz” sütunu aynı: 100. Üç yöntem de doğru sonucu veriyor ve üçü de 0 yeni öğe var ediyor — sonuçtaki nesnelerin hepsi ham verinin nesneleridir. Fark tamamen soldaki sütunda.

Elle tarama 15050 karşılaştırma yapıyor. Bu sayı iki parçadan gelir. İlk yüz öğe hep yeni olduğu için her biri o ana kadar birikmiş sonucun tamamıyla karşılaştırılır; bu 4950 eder. Kalan iki yüz öğe tekrardır ve her biri eşini bulunca durur; bunlar da 10100 eder. Toplam sayı, bir listeye sorulan üyelik sorusunun kaç kez sorulduğuyla değil, her sorunun kaç yuvayı geçtiğiyle büyüyor.

Kümeye vermek aynı işi 200 karşılaştırmayla bitiriyor — yaklaşık yetmiş beşte biri. İkisinin arasındaki fark bir başka yazımdan değil, bir başka soru sorma biçiminden geliyor: elle tarama her seferinde bütün sonucu geziyor, küme her seferinde tek bir bölmeye bakıyor. Ve 200 sayısının kendisi de anlamlıdır: ham veride tam 200 tekrar var. Küme her tekrar için bir karşılaştırma yapıyor, benzersiz öğeler için hiç yapmıyor. Öğe yeniyse bölmesi boştur ve karşılaştırılacak bir şey yoktur.

Üçüncü satır kümenin ödettiği bedeli ve onu ödemeden kurtulmanın yolunu birlikte veriyor. Küme sırasızdır; öğelerini hangi düzende verdiği bu derste ölçülmez ve ona dayanılmaz. Ama anahtarları ekleme sırasında tutan bir eşleme, aynı tekilleştirmeyi aynı 200 karşılaştırmayla yapıp sırayı da koruyor. Sonucun sıraya ihtiyacı varsa doğru araç küme değil, anahtar olarak kullanılan bir eşlemedir.

Küme İşlemleri

Kümenin ikinci işi kümeler arası hesaptır: birleşim, kesişim, fark, simetrik fark. Bu dört işlem küme kuramından gelir ve anlamları tartışmasızdır. Ölçülecek olan şey anlamları değil, neye mal oldukları: kaç öğe var ediyorlar, sonuç yeni bir kap mı, ve sonucun içindeki nesneler nereden geliyor.

• KL45 — Altı biçim de aynı üç öğelik kümenin tazeden kurulmuş bir kopyasıyla başlar; öğeler ölçümden önce bir kez var edilir.
• KL46 — İki küme bir öğede kesişir; kesişim ve fark sayıları bu yüzden önceden bilinir ve tabloyu doğrular.
• KL47 — “Öğeler havuzdan” sütunu, sonuçtaki her öğenin ölçüm öncesi havuzda is ile aranmasıyla bulunur.
• KL48 — Karmalanabilirlik doğrudan sınanır ve düşen istisnanın sınıf adı yazılır; karma değeri basılmaz.

"""Kume islemleri: her biri yeni kap kurar, hicbiri yeni oge var etmez."""

SAYAC = {"uretilen": 0}


class Oge:
    def __init__(self, deger):
        SAYAC["uretilen"] += 1
        self.deger = deger

    def __repr__(self):
        return f"Oge({self.deger})"


def sifirla():
    SAYAC["uretilen"] = 0


def uretilen():
    return SAYAC["uretilen"]


HAVUZ = [Oge(i) for i in range(5)]
SOL = {HAVUZ[0], HAVUZ[1], HAVUZ[2]}
SAG = {HAVUZ[2], HAVUZ[3], HAVUZ[4]}


def birlesim(a):
    return a | SAG


def kesisim(a):
    return a & SAG


def fark(a):
    return a - SAG


def simetrik_fark(a):
    return a ^ SAG


def yerinde_birlesim(a):
    a |= SAG
    return a


def yerinde_kesisim(a):
    a &= SAG
    return a


BICIMLER = (("a | b", birlesim), ("a & b", kesisim), ("a - b", fark),
            ("a ^ b", simetrik_fark), ("a |= b", yerinde_birlesim),
            ("a &= b", yerinde_kesisim))

print(f"{'işlem':<10s}{'yeni öğe':>9s}{'aynı kap':>10s}{'öğe':>5s}"
      f"{'öğeler havuzdan':>17s}")
for ad, islem in BICIMLER:
    a = set(SOL)
    once = a
    sifirla()
    sonuc = islem(a)
    havuzdan = all(any(x is y for y in HAVUZ) for x in sonuc)
    print(f"{ad:<10s}{uretilen():>9d}{str(sonuc is once):>10s}{len(sonuc):>5d}"
          f"{str(havuzdan):>17s}")

print()
print(f"{'sınama':<30s}{'sonuç'}")
print(f"{'SOL <= SOL | SAG':<30s}{SOL <= (SOL | SAG)}")
print(f"{'SOL < SOL':<30s}{SOL < SOL}")
print(f"{'SOL.isdisjoint(SAG)':<30s}{SOL.isdisjoint(SAG)}")
print(f"{'(SOL - SAG).isdisjoint(SAG)':<30s}{(SOL - SAG).isdisjoint(SAG)}")

print()
DONMUS = frozenset({HAVUZ[0], HAVUZ[1]})
print(f"dondurulmuş küme, kümenin öğesi olabilir -> {DONMUS in {DONMUS}}")
for aday in (SOL, DONMUS):
    try:
        {aday: 0}
        sonuc = "evet"
    except TypeError as e:
        sonuc = type(e).__name__
    print(f"{type(aday).__name__:<12s} anahtar olabilir -> {sonuc}")
try:
    {[1, 2]}
except TypeError as e:
    print(f"liste küme öğesi olabilir -> {type(e).__name__}")

işlem      yeni öğe  aynı kap  öğe  öğeler havuzdan
a | b             0     False    5             True
a & b             0     False    1             True
a - b             0     False    2             True
a ^ b             0     False    4             True
a |= b            0      True    5             True
a &= b            0      True    1             True

sınama                        sonuç
SOL <= SOL | SAG              True
SOL < SOL                     False
SOL.isdisjoint(SAG)           False
(SOL - SAG).isdisjoint(SAG)   True

dondurulmuş küme, kümenin öğesi olabilir -> True
set          anahtar olabilir -> TypeError
frozenset    anahtar olabilir -> evet
liste küme öğesi olabilir -> TypeError

Dört Hesap, Sıfır Öğe

Altı satırın “yeni öğe” sütunu tamamen 0 ve “öğeler havuzdan” sütunu tamamen True. Küme işlemleri hesap yapar, üretim yapmaz: sonuçta görünen her nesne ölçümden önce var edilmiş nesnelerden biridir. Bu, listelerde ve sözlüklerde ölçülen örüntünün üçüncü kez tekrarıdır — Python’un yerleşik kapları öğeleri taşımaz, onlara giden bağları düzenler.

Öğe sayıları kurguyu doğruluyor: üç ve üç öğelik, bir öğede kesişen iki kümenin birleşimi 5, kesişimi 1, farkı 2, simetrik farkı 4. Toplamların tutması ölçümün kendi iç denetimidir.

Ayrım yine “aynı kap” sütununda ve artık tanıdık: işleç biçimi yeni kap kuruyor, atamalı biçim var olanı değiştiriyor. Bu, bu kursta dördüncü kez aynı yerde çıkan ayrımdır — listede + ile +=, demette aynı ikilinin zorunlu yeniden kurması, sözlükte | ile |=, kümede | ile |=. Kural kaba özgü değil, dile özgüdür: işleç yeni nesne verir, atamalı işleç var olanı değiştirmeye çalışır.

Alt bloktaki alt küme sınamaları kümenin karşılaştırma anlamını veriyor. <= alt küme sorar ve bir küme kendisinin alt kümesidir; < öz alt küme sorar ve kendisi için False verir. Bu ikisi sayılarla değil, kümelerin kapsamıyla ilgilidir ve sayı karşılaştırmasıyla karıştırılmamalıdır.

Son blok değişmezlik ölçümünü kümeye taşıyor. Bir küme kendisi değiştirilebilir olduğu için karmalanamaz ve anahtar olamaz; TypeError ile düşüyor. Dondurulmuş küme (frozenset) aynı öğeleri değişmez bir kapta tutar ve hem anahtar olabiliyor hem başka bir kümenin öğesi olabiliyor. Liste ise ne anahtar ne öğe olabiliyor. Demetler dersinde kurulan kural burada da aynen işliyor: bir kabın başka bir kaba konabilmesinin koşulu, kendi içeriğinin sabit kalacağına dair verdiği sözdür.

Aynı Hesabı Listeyle Yapmak

Küme işlemlerinin hepsi listelerle de yazılabilir; hiçbiri kümeye özgü bir yetenek gerektirmez. Kesişim “soldakilerden sağdakinde de bulunanlar”, fark ise “soldakilerden sağdakinde bulunmayanlar” demektir ve ikisi de tek satırlık bir süzme ile yazılır. Bu yazımların sonucu doğrudur. Ölçülecek olan şey doğruluk değil, fiyattır.

• KL49 — İki koleksiyon iki yüzer öğedir ve yüz öğede çakışır; kesişim ve fark sonuçlarının yüzer öğe olması bu kurgudan bilinir ve tabloyu doğrular.
• KL50 — Liste ve küme biçimleri aynı nesnelerden kurulur; sayaç her satırdan hemen önce sıfırlanır ve kapların kurulması ölçüme girmez.
• KL51 — Son blok bir sayı ölçmez; kümenin yanıtlayabildiği ile yanıtlayamadığı soruyu ayırır.

"""Kesisimi elle almak ile kumeye vermek; ve tekillestirmenin dusurdugu bilgi."""


class Sayan:
    sayac = {"karsilastirma": 0}

    def __init__(self, d):
        self.d = d

    def __eq__(self, o):
        Sayan.sayac["karsilastirma"] += 1
        return isinstance(o, Sayan) and self.d == o.d

    def __hash__(self):
        return hash(self.d)


SOL_LISTE = [Sayan(i) for i in range(200)]
SAG_LISTE = [Sayan(i) for i in range(100, 300)]
SOL_KUME, SAG_KUME = set(SOL_LISTE), set(SAG_LISTE)


def elle_kesisim():
    return [x for x in SOL_LISTE if x in SAG_LISTE]


def kume_kesisim():
    return SOL_KUME & SAG_KUME


def elle_fark():
    return [x for x in SOL_LISTE if x not in SAG_LISTE]


def kume_fark():
    return SOL_KUME - SAG_KUME


print(f"{'işlem':<28s}{'karşılaştırma':>14s}{'sonuç öğesi':>13s}")
for ad, islem in (("kesişim, iki listeyle", elle_kesisim),
                  ("kesişim, iki kümeyle", kume_kesisim),
                  ("fark, iki listeyle", elle_fark),
                  ("fark, iki kümeyle", kume_fark)):
    Sayan.sayac["karsilastirma"] = 0
    sonuc = islem()
    print(f"{ad:<28s}{Sayan.sayac['karsilastirma']:>14d}{len(sonuc):>13d}")

print()
HAM = [Sayan(i % 100) for i in range(300)]
KUME = set(HAM)
print(f"ham veri {len(HAM)} öğe -> küme {len(KUME)} öğe")
print(f"kümeye sorulabilen soru: 'var mı' -> {Sayan(7) in KUME}")
print("kümeye sorulamayan soru: 'kaç kez geçti'")

işlem                        karşılaştırma  sonuç öğesi
kesişim, iki listeyle                25050          100
kesişim, iki kümeyle                   100          100
fark, iki listeyle                   25050          100
fark, iki kümeyle                      100          100

ham veri 300 öğe -> küme 100 öğe
kümeye sorulabilen soru: 'var mı' -> True
kümeye sorulamayan soru: 'kaç kez geçti'

Dört satırın “sonuç öğesi” sütunu doğruluğu bitiriyor: dördü de 100 öğe veriyor. Liste yazımı yanlış değil, yalnız pahalı. Kesişimi listelerle almak 25050, kümelerle almak 100 karşılaştırma yapıyor — iki yüz elli katı bir fark, aynı veride ve aynı sonuçla.

Fark satırları aynı sayıyı veriyor ve bu bir rastlantı değil. Liste yazımında her öğe için sağdaki liste taranıyor; taramanın “bulundu” ya da “bulunamadı” ile bitmesi, kaç yuva geçildiğini belirlemez. Kümede de aynı simetri var: kesişim eşleşen her öğe için bir karşılaştırma yapıyor, fark da aynısını. Erişim biçimi değişince maliyetin şekli değişiyor, yalnız büyüklüğü değil.

Son blok kümenin sınırını çiziyor ve bu ders için son sözdür. Üç yüz öğelik veri kümeye verildiğinde 100 öğeye iniyor. Kaybolan şey iki yüz nesne değil — nesneler duruyor, ham liste onları hâlâ tutuyor. Kaybolan şey bilgidir: hangi değerin kaç kez geçtiği. Küme “var mı” sorusunu bir karşılaştırmayla yanıtlar, ama “kaç kez” sorusunu hiç yanıtlayamaz, çünkü o sayıyı hiç tutmaz. Tekilleştirme ucuzdur; ucuzluğunun kaynağı, atılan bilginin geri istenmeyeceği varsayımıdır.

Özet

• Üç yüz öğeli veride tekilleştirme elle tarandığında 15050, kümeye verildiğinde 200 karşılaştırma yapar; üç yöntem de aynı 100 benzersiz öğeyi ve 0 yeni öğe verir.
• Kümenin 200 sayısı ham verideki tekrar sayısına eşittir: her tekrar bir karşılaştırma ister, benzersiz öğe hiç istemez.
• Küme sırasızdır; sıra korunacaksa aynı 200 karşılaştırmayı yapıp ekleme sırasını da tutan bir eşleme kullanılır.
• Altı küme işleminin altısı da 0 öğe var eder ve sonuçtaki her nesne eskidir; işleç biçimi yeni kap kurar, atamalı biçim var olanı değiştirir.
• Küme değiştirilebilir olduğu için anahtar olamaz; dondurulmuş küme hem anahtar hem küme öğesi olabilir — koşul, kabın içeriğinin sabit kalacağına dair verdiği sözdür.
• Aynı kesişimi listelerle almak 25050, kümelerle almak 100 karşılaştırma yapar; ikisi de aynı 100 öğeyi verir, ama tekilleştirme “kaç kez geçti” bilgisini düşürür.

Sonraki Adım

Bu dersin son satırı kümenin yanıtlayamadığı soruyu yazdı: kaç kez. O soruyu tutmak isteyen herkes aynı kalıbı elle yazar — bir sözlük açar, anahtar varsa artırır, yoksa birden başlatır. Aynı biçimde elle yazılan başka kalıplar da vardır: bir listenin iki ucundan da öğe almak, olmayan anahtar için boş bir kap hazırlamak. Sonraki ders bu kalıpların standart kitaplıktaki hazır karşılıklarına bakar ve her birini elle yazılan eşdeğeriyle yan yana koyar. Ölçülecek iki sayı var: kaç satır ve kaç nesne.