Sözlükler

Önceki ders bir demetin anahtar olabildiğini gösterdi ve anahtarın kimlikle değil eşitlikle bulunduğunu ölçtü. Anahtarı alıp değere ulaştıran kabın kendisi ise ölçülmedi.

Sözlük (dict), anahtarı değere bağlayan kaptır. Bu ders ona iki soru sorar ve ikisinin de yanıtı sayıdır. Birincisi kursun dördüncü okumasının ilk yarısıdır: aynı iki yüz öğe bir listede ve bir kümede arandığında kaç karşılaştırma yapılır? Veri aynı, öğeler aynı; değişen tek şey onları hangi kapta tuttuğumuz. İkincisi kopyalamayla ilgilidir: bir sözlüğün anahtarlarını istediğimizde elimize geçen şey bir kopya mı, yoksa sözlüğe bakmayı sürdüren bir pencere mi?

Eşleme Neye Bakar

Bir liste bir öğeyi ararken elinde tek bir yol vardır: yuvaları sırayla gezmek ve her birini aranana eşit mi diye sormak. Sözlük ve küme başka bir yol kullanır — anahtarın karma değerinden onun hangi bölmeye düştüğünü hesaplar ve doğrudan oraya bakar. Bu yüzden ikisinin de anahtarı karmalanabilir olmak zorundadır; önceki dersin ölçtüğü koşul buydu.

Bu düzeneğin kendisi bu kursun konusu değildir. Karma tablosunun nasıl kurulduğu, yük çarpanı, çakışma çözümü ve tablonun büyüme davranışı Veri Yapıları kursunda kuruldu; karmaşıklık çözümlemesi ve büyüme sınıfları Algoritmalar kursunda kuruldu. İkisi de burada tekrarlanmaz. Orada düzenek kuruldu; burada Python’un o düzeneği hangi kapla verdiği ve tek bir sınamanın kaç somut karşılaştırmaya mal olduğu ölçülüyor. Aşağıdaki sayılar bir büyüme sınıfı iddiası değildir; belirli bir veriyle yapılmış bir sayımdır.

• KL25 — Karşılaştırmayı öğenin kendisi sayar: eşitlik yöntemi her çağrıldığında ortak bir sayacı bir artırır. Kâhin kurgudur; sayı bir tahmin değil bir dökümdür.
• KL26 — Üç kap aynı iki yüz öğeden kurulur; öğeler bir kez var edilir ve üç kap da aynı nesnelere bakar.
• KL27 — Sayaç her sınamadan hemen önce sıfırlanır; kapların kurulması sırasında yapılan karşılaştırmalar ölçüme girmez.
• KL28 — Aranan öğe her seferinde yeniden kurulur; böylece arama kimlikle değil eşitlikle yapılmak zorunda kalır.
• KL29 — İki durum ayrı ayrı ölçülür: kapta bulunan bir öğe ve kapta bulunmayan bir öğe.
• KL30 — Listedeki konum etkisi ayrıca ölçülür; ilk, ortadaki ve son öğe için sayı ayrı okunur.

"""Ayni iki yuz oge, uc kap: uyelik sinamasi kac karsilastirma yapiyor."""


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)


def olc(kap, aranan):
    Sayan.sayac["karsilastirma"] = 0
    bulundu = aranan in kap
    return Sayan.sayac["karsilastirma"], bulundu


N = 200
OGELER = [Sayan(i) for i in range(N)]
KAPLAR = (("liste", list(OGELER)), ("küme", set(OGELER)),
          ("sözlük", {o: o.d for o in OGELER}))

print(f"{'kap':<8s}{'son öğe aranıyor':>18s}{'bulundu':>9s}"
      f"{'olmayan öğe aranıyor':>22s}{'bulundu':>9s}")
for ad, kap in KAPLAR:
    var, b1 = olc(kap, Sayan(N - 1))
    yok, b2 = olc(kap, Sayan(N))
    print(f"{ad:<8s}{var:>18d}{str(b1):>9s}{yok:>22d}{str(b2):>9s}")

print()
ilk_var, _ = olc(KAPLAR[0][1], Sayan(0))
orta_var, _ = olc(KAPLAR[0][1], Sayan(N // 2))
print(f"listede ilk öğe {ilk_var} | ortadaki öğe {orta_var} | "
      f"son öğe {olc(KAPLAR[0][1], Sayan(N - 1))[0]}")
print(f"kümede ilk öğe {olc(KAPLAR[1][1], Sayan(0))[0]} | "
      f"ortadaki öğe {olc(KAPLAR[1][1], Sayan(N // 2))[0]} | "
      f"son öğe {olc(KAPLAR[1][1], Sayan(N - 1))[0]}")

print()
SOZLUK = KAPLAR[2][1]
Sayan.sayac["karsilastirma"] = 0
deger = SOZLUK[Sayan(N - 1)]
print(f"sözlükten değer okumak: {Sayan.sayac['karsilastirma']} karşılaştırma, "
      f"dönen değer {deger}")

kap       son öğe aranıyor  bulundu  olmayan öğe aranıyor  bulundu
liste                  200     True                   200    False
küme                     1     True                     0    False
sözlük                   1     True                     0    False

listede ilk öğe 1 | ortadaki öğe 101 | son öğe 200
kümede ilk öğe 1 | ortadaki öğe 1 | son öğe 1

sözlükten değer okumak: 1 karşılaştırma, dönen değer 199

İki Yüze Karşı Bir

Üst tablonun ilk sütunu kursun dördüncü okumasını veriyor: aynı öğeyi aramak listede 200, kümede ve sözlükte 1 karşılaştırma yapıyor. Veri aynı, öğeler aynı nesneler, aranan aynı değer. Değişen tek şey erişim biçimi. Maliyeti veri değil, erişim biçimi belirliyor.

İkinci sütun ayrımı daha da keskinleştiriyor. Kapta bulunmayan bir öğe arandığında liste yine 200 karşılaştırma yapıyor — bulamadığını anlamak için hepsine bakmak zorunda. Küme ve sözlük ise 0 karşılaştırma yapıyor: karma hesabı onu boş bir bölmeye götürdü ve orada karşılaştıracak bir şey bulamadı. Yokluğu kanıtlamak listede en pahalı iş, kümede ise en ucuzudur.

Ortadaki iki satır listenin sayısının tek bir sayı olmadığını gösteriyor: ilk öğe 1, ortadaki 101, son öğe 200 karşılaştırma. Listede maliyet aranan şeyin nerede durduğuna bağlıdır. Kümede aynı üç arama 1, 1, 1 veriyor — konum ölçüme hiç girmiyor, çünkü küme yuvaları gezmiyor, hesaplıyor.

Son satır sözlüğün asıl işini ölçüyor. Bir anahtardan değere ulaşmak 1 karşılaştırma yapıyor; küme üyeliğiyle aynı sayı. Sözlük, kümenin yaptığı aramayı yapıp bulduğu yerde değeri de tutar. İkisi aynı düzeneğin iki yüzüdür: küme yalnız “var mı” der, sözlük “var, ve karşılığı bu” der.

Görünüm mü, Anlık Kopya mı

Sözlüğün anahtarlarını, değerlerini ya da çiftlerini isteyen yazımlar bir liste döndürmez. Döndürdükleri şey bir görünümdür (view): sözlüğe bakmayı sürdüren, kendi yuvası olmayan bir nesne. Bunun karşıtı anlık kopyadır (snapshot) — istendiği andaki durumu ayrı bir kapta dondurup sözlükle bağını koparan liste. İkisi aynı anda kurulup sözlük değiştirildiğinde fark ölçülebilir hâle gelir.

• KL31 — Üç görünüm ve bir anlık kopya aynı anda, sözlüğe dokunulmadan önce kurulur; sonra tek bir anahtar eklenir ve dördü de yeniden okunur.
• KL32 — Uzunluk her kaptan kendi yöntemiyle okunur; ölçüm bir kabın uzunluğunu başka bir kaptan çıkarmaz.
• KL33 — Bin girdilik ölçümde anlık kopyanın yuva sayısı basılır; görünümün yuva sayısı basılmaz, çünkü görünüm yuva tutmaz.
• KL34 — İki görünüm nesnesi hem is hem == ile karşılaştırılır; kimlik değeri basılmaz, yalnız aynılık sınanır.
• KL35 — Dolaşma sırasında değişiklik iki kez denenir: bir kez görünüm üzerinde, bir kez anlık kopya üzerinde. İstisnayla biten deneme kesilmeden önce bir anahtar eklemiştir ve ikinci deneme o durumdan devam eder.
• KL36 — Sıra ölçümünde üç anahtarlı küçük bir sözlük kullanılır; sıra, anahtar listesinin kendisinden okunur.

"""Gorunum ile anlik kopya: hangisi sonradan eklenen anahtari goruyor."""

sozluk = {"a": 1, "b": 2}
anahtarlar = sozluk.keys()
degerler = sozluk.values()
ciftler = sozluk.items()
liste = list(sozluk.keys())

onceki = (len(anahtarlar), len(degerler), len(ciftler), len(liste))
sozluk["c"] = 3
sonraki = (len(anahtarlar), len(degerler), len(ciftler), len(liste))

print(f"{'kap':<22s}{'eklemeden önce':>15s}{'sonra':>7s}"
      f"{'yeni anahtarı görüyor':>23s}")
for ad, once, sonra, icerir in (
        ("keys() görünümü", onceki[0], sonraki[0], "c" in anahtarlar),
        ("values() görünümü", onceki[1], sonraki[1], 3 in degerler),
        ("items() görünümü", onceki[2], sonraki[2], ("c", 3) in ciftler),
        ("list(keys()) kopyası", onceki[3], sonraki[3], "c" in liste)):
    print(f"{ad:<22s}{once:>15d}{sonra:>7d}{str(icerir):>23s}")

print()
buyuk = {i: i for i in range(1000)}
gorunum = buyuk.keys()
anlik = list(buyuk.keys())
print(f"bin girdilik sözlükte görünümün yuvası yoktur; anlık kopyanın yuvası "
      f"{len(anlik)}")
print(f"gorunum is buyuk.keys() -> {gorunum is buyuk.keys()} | "
      f"gorunum == buyuk.keys() -> {gorunum == buyuk.keys()}")

print()
try:
    for anahtar in buyuk:
        if anahtar == 3:
            buyuk[1000] = 1000
except RuntimeError as e:
    print(f"görünüm üzerinde dolaşırken ekleme: {type(e).__name__}")
kopya_uzerinde = 0
for anahtar in list(buyuk):
    if anahtar == 3:
        buyuk[1001] = 1001
    kopya_uzerinde += 1
print(f"anlık kopya üzerinde dolaşırken ekleme: sorunsuz, "
      f"{kopya_uzerinde} tur döndü, sözlük {len(buyuk)} girdiye çıktı")

print()
sira = {"kuzey": 1, "yamac": 2, "ozet": 3}
print(f"ekleme sırası: {list(sira)}")
del sira["kuzey"]
sira["kuzey"] = 9
print(f"silinip yeniden eklendikten sonra: {list(sira)}")
sira["yamac"] = 20
print(f"var olan anahtarın değeri değişince: {list(sira)}")

kap                    eklemeden önce  sonra  yeni anahtarı görüyor
keys() görünümü                     2      3                   True
values() görünümü                   2      3                   True
items() görünümü                    2      3                   True
list(keys()) kopyası                2      2                  False

bin girdilik sözlükte görünümün yuvası yoktur; anlık kopyanın yuvası 1000
gorunum is buyuk.keys() -> False | gorunum == buyuk.keys() -> True

görünüm üzerinde dolaşırken ekleme: RuntimeError
anlık kopya üzerinde dolaşırken ekleme: sorunsuz, 1001 tur döndü, sözlük 1002 girdiye çıktı

ekleme sırası: ['kuzey', 'yamac', 'ozet']
silinip yeniden eklendikten sonra: ['yamac', 'ozet', 'kuzey']
var olan anahtarın değeri değişince: ['yamac', 'ozet', 'kuzey']

Pencere Kapanmıyor

Üst tablo dört satırın üçünü aynı yana koyuyor. Üç görünümün de uzunluğu 2’den 3’e çıkıyor ve üçü de sonradan eklenen anahtarı görüyor. Anlık kopya 2’de kalıyor ve görmüyor. Görünümler ekleme anında var bile değillerdi — kurulduklarında sözlük iki girdiliydi. Ama onların taşıdığı şey iki girdi değil, sözlüğün kendisine giden bir bağdı; sözlük değişince gördükleri de değişti.

İkinci blok bunun bedelini ve kazancını yan yana koyuyor. Bin girdilik sözlükte anlık kopya 1000 yuva açıyor — her biri bir anahtara giden bağ. Görünüm hiç yuva açmıyor; ne kadar büyük sözlüğe bakarsa baksın taşıdığı şey tek bir bağdır. Bir sözlüğün anahtarları üzerinde yalnız dolaşılacaksa anlık kopya çıkarmak bin yuvalık bir bedeldir ve karşılığında hiçbir şey alınmaz. Görünüm nesnesinin kendisi her istendiğinde yeniden kuruluyor — gorunum is buyuk.keys() False — ama iki görünüm eşit sayılıyor, çünkü ikisi de aynı sözlüğe bakıyor.

Karşılığında ödenen şey üçüncü bloktadır. Görünüm üzerinde dolaşırken sözlüğe anahtar eklemek RuntimeError veriyor: sözlük dolaşma sırasında büyüdüğünde görünümün nereye baktığı belirsizleşir ve dil bunu bir kusur sayıp döngüyü keser. Aynı iş anlık kopya üzerinde sorunsuz yürüyor — kopya çıkarıldığı andaki durumu taşır, sözlük sonradan ne olursa olsun tur sayısı değişmez. İkinci ölçümün 1001 turla başlaması, kesilen ilk döngünün istisnadan önce bir anahtar eklemiş olmasındandır.

Kural buradan çıkıyor: dolaşırken değiştirilecekse anlık kopya alınır, yalnız okunacaksa görünüm kullanılır. Anlık kopyanın bedeli yuva, görünümün bedeli kırılganlıktır.

Son üç satır sıralamayı gösteriyor. Anahtarlar ekleme sırasında duruyor. Silinip yeniden eklenen anahtar başa değil sona gidiyor, çünkü yeniden ekleme yeni bir girdidir. Var olan bir anahtarın değerini değiştirmek ise sırayı hiç bozmuyor — girdinin yeri korunuyor, yalnız değeri yenileniyor.

Birleştirmenin ve Aramanın Yazımları

Listelerde + ile += ayrımı yeni kap kurmakla var olanı büyütmek arasındaydı. Sözlükte aynı ayrım vardır ve beş ayrı yazımla karşımıza çıkar. Yanına bir de arama tarafı konur: var olmayan bir anahtar istendiğinde beş yazım beş ayrı şey yapar.

• KL37 — Beş biçim de aynı üç girdilik sözlüğün tazeden kurulmuş bir kopyasıyla başlar; değer nesneleri ölçümden önce bir kez var edilir.
• KL38 — Sağdaki sözlük soldakiyle bir anahtarda çakışır; böylece birleşmenin anahtar sayısını nasıl bulduğu görünür.
• KL39 — Arama tarafında düşen istisnanın sınıf adı yazılır; dönen değer varsa doğrudan basılır.

"""Sozlugu birlestirmenin bicimleri ve var olmayan anahtarin bes yaziminda karsiligi."""

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"]


DEGERLER = {ad: Oge(i) for i, ad in enumerate(("kuzey", "yamac", "ozet", "guney"))}
SOL = {"kuzey": DEGERLER["kuzey"], "yamac": DEGERLER["yamac"],
       "ozet": DEGERLER["ozet"]}
SAG = {"ozet": DEGERLER["guney"], "guney": DEGERLER["guney"]}


def birlestir(d):
    return d | SAG


def yerinde_birlestir(d):
    d |= SAG
    return d


def guncelle(d):
    d.update(SAG)
    return d


def kopyala(d):
    return dict(d)


def acarak_kur(d):
    return {**d, **SAG}


BICIMLER = (("d | e", birlestir), ("d |= e", yerinde_birlestir),
            ("d.update(e)", guncelle), ("dict(d)", kopyala),
            ("{**d, **e}", acarak_kur))

print(f"{'biçim':<14s}{'yeni öğe':>9s}{'aynı kap':>10s}{'anahtar':>9s}"
      f"{'değerler paylaşılıyor':>23s}")
for ad, islem in BICIMLER:
    d = dict(SOL)
    once = d
    sifirla()
    sonuc = islem(d)
    paylasim = all(any(v is x for x in DEGERLER.values())
                   for v in sonuc.values())
    print(f"{ad:<14s}{uretilen():>9d}{str(sonuc is once):>10s}"
          f"{len(sonuc):>9d}{str(paylasim):>23s}")

print()
birlesik = SOL | SAG
print(f"çakışan anahtar 'ozet' -> {birlesik['ozet']} | "
      f"sağdaki değerle aynı nesne: {birlesik['ozet'] is SAG['ozet']}")

print()
print(f"{'yazım':<24s}{'sonuç'}")
try:
    SOL["bozuk"]
except KeyError as e:
    print(f"{'d[yok]':<24s}{type(e).__name__}")
print(f"{'d.get(yok)':<24s}{SOL.get('bozuk')}")
print(f"{'d.get(yok, varsayılan)':<24s}{SOL.get('bozuk', Oge(9))}")
print(f"{'d.pop(yok, varsayılan)':<24s}{SOL.pop('bozuk', Oge(9))}")
print(f"{'yok in d':<24s}{'bozuk' in SOL}")

biçim          yeni öğe  aynı kap  anahtar  değerler paylaşılıyor
d | e                 0     False        4                   True
d |= e                0      True        4                   True
d.update(e)           0      True        4                   True
dict(d)               0     False        3                   True
{**d, **e}            0     False        4                   True

çakışan anahtar 'ozet' -> Oge(3) | sağdaki değerle aynı nesne: True

yazım                   sonuç
d[yok]                  KeyError
d.get(yok)              None
d.get(yok, varsayılan)  Oge(9)
d.pop(yok, varsayılan)  Oge(9)
yok in d                False

Beş biçimin beşi de 0 yeni değer var ediyor ve beşinde de değerler paylaşılıyor. Sözlük, listenin yaptığını anahtar tarafında yapıyor: taşıdığı şey değerler değil, onlara giden bağlar. Ayrım yine “aynı kap” sütununda — d | e, dict(d) ve {**d, **e} yeni bir kap kuruyor, d |= e ile d.update(e) var olanı büyütüyor.

Anahtar sayısı üçle ikinin toplamı olan beş değil, 4. Çakışan anahtar iki kez sayılmıyor; sağdaki değer soldakini eziyor ve birlesik['ozet'] is SAG['ozet'] bunu doğruluyor. Bir sözlüğü birleştirmenin sonucu bu yüzden öngörülebilir bir sayı değildir — çakışma sayısına bağlıdır ve çakışmayı ancak anahtarlar söyler.

Alt tablo var olmayan bir anahtarın beş yazımdaki karşılığını veriyor. Yalnız köşeli ayraçla erişim istisna üretiyor; kalan dördü değer döndürüyor. get varsayılan verilmediğinde None veriyor ve bu bir kusur bildirimi değildir — sözlükte None değerli bir anahtar da bulunabilirdi, dolayısıyla None dönmesi “yok” demenin kesin yolu değildir. Yokluğu kesin sınayan tek yazım üyelik sınamasıdır ve o da bu dersin ilk ölçümündeki 1 ya da 0 karşılaştırmayla yapılır.

Özet

• Aynı iki yüz öğede üyelik sınaması listede 200, kümede ve sözlükte 1 karşılaştırma yapar; bulunmayan öğe arandığında liste yine 200, küme ve sözlük 0 yapar.
• Listenin sayısı konuma bağlıdır — ilk öğe 1, ortadaki 101, son öğe 200; kümede üç arama da 1’dir, çünkü küme yuvaları gezmez, hesaplar.
• keys(), values() ve items() birer görünümdür: sözlüğe bakmayı sürdürürler ve sonradan eklenen anahtarı görürler — uzunlukları 2’den 3’e çıkar. list(...) ile alınan anlık kopya 2’de kalır.
• Görünüm yuva tutmaz; bin girdilik sözlüğün anlık kopyası 1000 yuva açar. Karşılığında görünüm üzerinde dolaşırken sözlüğe eklemek RuntimeError verir, anlık kopya üzerinde vermez.
• Anahtarlar ekleme sırasında durur; silinip yeniden eklenen anahtar sona gider, var olan bir anahtarın değerini değiştirmek sırayı bozmaz.

Sonraki Adım

Bu dersin ölçümünde küme, sözlüğün yanında sessizce durdu ve aynı sayıları verdi — 1 ve 0. Kendi başına ne yaptığı sorulmadı. Sonraki ders yalnız kümeye bakar ve onun en sık kullanılan işini ölçer: bir listedeki tekrarları atmak. Soru yine sayıyla yanıtlanacak. Tekrarları elle ayıklamak ile kümeye vermek kaç karşılaştırmaya ve kaç nesneye mal oluyor, ve kümeden geri dönen kapta öğeler yeni mi, eski mi?