Sözlükler, kümeler ve hash sezgisi

Programlama Temelleri dersinde dict ve set yapılarını temel düzeyde kullandınız. Bu hafta aynı sözdizimini yeniden öğrenmeyeceğiz. Bunun yerine hangi işlem için hangi koleksiyonun uygun olduğunu, sözlük ve kümelerin üyelik kontrolünde neden güçlü olduğunu ve hash tabanlı erişim fikrini sezgisel düzeyde inceleyeceğiz.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

• dict ile anahtar-değer ilişkisini problem bağlamında kurabilmeli,
• set ile benzersizlik ve hızlı üyelik kontrolünü kullanabilmeli,
• Frekans sayımı, gruplama ve kayıt indeksleme yapabilmeli,
• Liste, sözlük ve küme arasında işlem gereksinimine göre seçim yapabilmeli,
• Hash fikrini matematiksel ayrıntıya girmeden açıklayabilmeli,
• Hashable olma fikrini sözlük anahtarı ve küme elemanı olabilme koşuluyla ilişkilendirebilmeli,
• Hash çakışmasının neden mümkün olduğunu ve bu nedenle ortalama durum ifadesinin neden önemli olduğunu sezgisel düzeyde açıklayabilmelisiniz.

2 Liste mi, sözlük mü?

Bir öğrenci listesini yalnızca sırayla dolaşacaksak liste uygun olabilir:

students = ["Ayşe", "Bora", "Cem"]

Fakat öğrenci numarasına göre sık sık arama yapacaksak farklı bir temsil daha anlamlıdır:

students = {
    101: "Ayşe",
    102: "Bora",
    103: "Cem"
}

Burada soru artık “listede kaçıncı sırada?” değil, “101 anahtarına karşılık gelen değer nedir?” olur.

3 Sözlüğü indeks olarak düşünmek

Sözlük, bir bilgiyi başka bir bilgi üzerinden bulmak için kullanılabilir. Örneğin ürün kodundan ürün bilgisine geçelim:

Bu kullanımda sözlük bir indeks (index) görevi görür: bir anahtardan ilgili kayda hızlıca ulaşmamızı sağlar.

4 Küme: benzersizlik ve üyelik

Küme, aynı değeri yalnızca bir kez tutar:

Kümenin en güçlü kullanım alanlarından biri şudur:

Bu değer daha önce görüldü mü?

Örneğin tekrar eden kullanıcı adlarını bulalım:

5 Frekans sayımı

Bir listedeki her değerin kaç kez görüldüğünü hesaplamak için sözlük çok uygundur:

Aynı kalıbı daha kısa biçimde dict.get() ile yazabiliriz:

Tip

get(key, default) yöntemi, anahtar yokken hata üretmek yerine verdiğiniz varsayılan değeri döndürür. Frekans sayımında 0 iyi bir başlangıç değeridir.

6 Alıştırma — frekans tablosu

Aşağıdaki programda notların kaç kez tekrarlandığını counts sözlüğünde tutun.

Beklenen sonuç:

{70: 3, 80: 2, 90: 1}

counts[grade] = counts.get(grade, 0) + 1 kalıbını kullanabilirsiniz.

grades = [70, 80, 70, 90, 80, 70]
counts = {}

for grade in grades:
    counts[grade] = counts.get(grade, 0) + 1

print(counts)

7 Gruplama

Frekans sayımında her anahtar için bir sayı tutuyorduk. Gruplamada ise her anahtar için bir liste tutabiliriz:

Bu kalıbı ilerleyen haftalarda dosyadan gelen kayıtları gruplarken tekrar kullanacağız.

8 Hash nedir? Sezgisel model

Sözlük ve kümenin hızlı üyelik/erişim davranışını anlamak için hash fikrini tanıyalım.

Bir hash fonksiyonunu, bir anahtardan o anahtar için kullanılabilecek sayısal bir özet üreten mekanizma gibi düşünebilirsiniz. Python bu değerden yararlanarak aramayı küçük bir aday bölgesine yönlendirebilir. Bu nedenle çoğu durumda bütün elemanları baştan sona dolaşmak gerekmez.

flowchart LR
    A["anahtar: D205"] --> B["hash değeri"]
    B --> C["olası konum"]
    C --> D["Defter kaydı"]

Bu görsel gerçek Python bellek düzenini birebir göstermez; yalnızca neden tüm kayıtları sırayla aramak zorunda kalmayabiliriz? sorusuna sezgisel bir model verir.

9 Çakışma (collision) neden mümkündür?

Hash tablosundaki olası konum sayısı sınırlıdır; kullanılabilecek anahtar sayısı ise çok daha fazla olabilir. Bu nedenle iki farklı anahtarın aynı aday konuma yönelmesi mümkündür. Buna hash çakışması (collision) denir.

flowchart LR
    A["anahtar A"] --> H1["hash"]
    B["anahtar B"] --> H2["hash"]
    H1 --> C["aynı aday bölge"]
    H2 --> C
    C --> R["çakışmayı çözme mekanizması"]

Python’ın kullandığı gerçek çözüm ayrıntıları bu dersin kapsamında değildir. Bizim için önemli sonuç şudur:

Hash tabanlı erişim çoğu durumda çok hızlıdır; fakat bu, her olası durumda kesin ve değişmez O(1) garanti anlamına gelmez.

Important

Bu derste dict ve set işlemlerini karar verirken ortalama durumda O(1) sezgisiyle düşüneceğiz. Çakışmalar, tablonun doluluk durumu ve gerçekleştirim ayrıntıları nedeniyle en kötü durum davranışı farklı olabilir.

10 hashable ne demektir?

Bir nesnenin sözlük anahtarı veya normal bir küme elemanı olabilmesi için Python açısından hashable olması gerekir. Basitçe, nesnenin kullanılabilir bir hash değerinin bulunması ve eşitlik ilişkisi açısından bu değerin güvenilir kalması gerekir.

Birçok değiştirilemez temel tür hashable’dır:

• int
• str
• Uygun elemanlardan oluşan tuple

Buna karşılık yaygın mutable koleksiyonlar genellikle hashable değildir:

• list
• dict
• set

Burada teknik ölçüt doğrudan “mutable mı?” sorusu değil, hashable mı? sorusudur. Mutability ise neden birçok koleksiyonun hashable olmamasını beklediğimizi anlamaya yardımcı olur.

11 Neden liste anahtar olamaz?

Aşağıdaki kodu çalıştırın:

Liste hashable olmadığı için sözlük anahtarı olarak kullanılamaz. Aynı şekilde normal bir set de başka bir kümenin normal elemanı olamaz.

Buna karşılık bir tuple, içindeki bütün elemanlar da hashable ise anahtar olabilir:

Ancak her tuple otomatik olarak hashable değildir:

İçteki liste hashable olmadığı için tuple da sözlük anahtarı olarak kullanılamaz.

12 Tahmin et — hangileri hashable?

Aşağıdaki değerlerin her biri için önce tahmininizi yapın, sonra kodu çalıştırın:

Bu etkinlikte ezberlenecek uzun bir tür listesi yerine şu soruyu alışkanlık hâline getirin:

Bu değeri sözlük anahtarı veya küme elemanı yapmak istiyorsam Python onu hashable kabul ediyor mu?

13 Alıştırma — uygun anahtarı seç

Bir koordinatı sözlük anahtarı olarak tutmak istiyorsunuz. Aşağıdaki kodda key değerini hashable bir yapı olacak biçimde düzenleyin.

key = (41.29, 36.33) kullanabilirsiniz.

key = (41.29, 36.33)
locations = {}
locations[key] = "Samsun"
print(locations)

14 İşlem gereksinimine göre seçim

Gereksinim	Genellikle uygun yapı
Sırayı ve tekrarları korumak	list
Anahtardan değere ulaşmak	dict
Benzersiz değerler	set
Çok sık üyelik kontrolü	çoğu zaman set veya dict
Aynı değerin kaç kez geçtiğini saymak	dict
Bir anahtara birden çok kayıt bağlamak	dict + list

15 Tahmin et — hangi yapı daha doğal?

Aşağıdaki durumların her biri için önce kendi seçiminizi yapın:

1. Bir sınavdaki öğrenci cevaplarını sırayla saklamak.
2. Kullanılmış e-posta adreslerini tekrar kabul etmemek.
3. Plaka kodundan şehir adına ulaşmak.
4. Metindeki kelimelerin kaç kez geçtiğini bulmak.
5. Ürünleri kategoriye göre gruplamak.

Tek bir “her zaman en iyi” veri yapısı yoktur. Doğru soru şudur:

Program en sık hangi işlemi yapacak?

16 Bölüm özeti

• Sözlük, anahtar-değer ilişkisi ve indeksleme için uygundur.
• Küme, benzersizlik ve üyelik kontrolünde kullanışlıdır.
• Frekans sayımı dict ile doğal biçimde modellenir.
• Gruplamada sözlük değerleri liste olabilir.
• Hash, anahtardan hızlı erişim için kullanılan temel fikirdir.
• İki farklı anahtar aynı aday konuma yönlenebilir; buna hash çakışması denir.
• Sözlük anahtarı ve normal küme elemanı olabilmek için temel teknik koşul hashable olmaktır.
• Hash tabanlı yapıların O(1) davranışı bu derste ortalama durum sezgisi olarak kullanılmalıdır.
• Veri yapısı seçimi, sözdizimine değil işlem gereksinimine dayanır.

17 Kendinizi kontrol edin

1. dict ile set arasındaki temel model farkı nedir?
2. Frekans sayımı neden liste yerine sözlükle daha doğal ifade edilir?
3. x in some_set işlemi hangi problem türlerinde değerlidir?
4. Hash sezgisini bir cümleyle nasıl açıklarsınız?
5. Hash çakışması ne demektir?
6. Sözlük anahtarı için teknik ölçüt neden yalnızca “immutable” sözcüğüyle açıklanmamalıdır?
7. (1, 2) hashable iken (1, [2, 3]) neden hashable değildir?