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öz dizimini yeniden öğrenmeyeceğiz. Bunun yerine üç soruya bakacağız: Hangi işlem için hangi koleksiyon uygun? Sözlük ve küme, bir değerin içlerinde olup olmadığını neden hızlı cevaplar? Hash tabanlı erişim ne demektir?

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • Bir problemdeki anahtar-değer ilişkisini görüp dict ile kurabilmeli,
  • set ile benzersizlik ve hızlı üyelik kontrolünü kullanabilmeli,
  • Frekans sayımı (her değerin kaç kez geçtiğini sayma), 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,
  • Sözlük anahtarı ya da küme elemanı olabilmek için hashable olmak gerektiğini bilmeli,
  • Hash çakışmasının neden olabildiğini ve maliyeti bu yüzden “ortalama durumda” diye söylediğimizi 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"]

Ama öğrencileri numarasına göre sık sık arayacaksak başka bir yapı daha uygun olur:

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ükle bir bilgiyi başka bir bilgiden yola çıkarak bulabiliriz. Örneğin ürün kodundan ürünün bilgilerine ulaşalım:

Burada sözlük bir indeks (index) gibi çalışır: kitabın sonundaki dizin gibi, bizi anahtardan o anahtarın kaydına hızlıca götürür.

4 Küme: benzersizlik ve üyelik

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

Kümenin en çok işe yaradığı sorulardan 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) metodu, anahtar yoksa hata vermez; 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 her notun kaç kez geçtiğini counts sözlüğünde sayın.

Beklenen çıktı:

{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 üyelik sorusuna ve anahtarla erişime neden hızlı cevap verdiğini anlamak için hash fikrini tanıyalım.

Hash fonksiyonu bir anahtardan bir sayı hesaplar. Bu sayıya anahtarın hash değeri denir. Python bu değere bakarak anahtarın hash tablosunda (sözlük ve kümenin verileri tuttuğu yapı) nerede durabileceğini bulur ve aramayı küçük bir bölgeyle sınırlar. Bu yüzden ç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 şema Python’ın veriyi bellekte nasıl tuttuğunu birebir göstermez. Yalnızca bütün kayıtları neden sırayla aramak zorunda kalmadığımızı sezgisel olarak anlatır.

9 Çakışma (collision) neden olabilir?

Hash tablosundaki konum sayısı sınırlıdır, kullanılabilecek anahtar sayısı ise çok daha fazla olabilir. Bu yüzden iki farklı anahtar aynı konuma düşebilir. 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 çakışmaları nasıl çözdüğü bu dersin konusu değil. Bizim için sonuç şu:

Hash tabanlı erişim çoğu durumda çok hızlıdır, ama her durumda O(1) olacağının garantisi yoktur.

Important

Bu derste yapı seçerken dict ve set işlemlerini ortalama durumda O(1) kabul edeceğiz. En kötü durumda ise çakışmalar, tablonun ne kadar dolu olduğu ve gerçekleştirim ayrıntıları yüzünden maliyet farklı olabilir.

10 hashable ne demektir?

Bir nesnenin sözlük anahtarı ya da küme elemanı olabilmesi için hashable olması gerekir. Kabaca şöyle: nesnenin bir hash değeri olmalı, bu değer nesne var olduğu sürece değişmemeli ve birbirine eşit iki nesnenin hash değeri de aynı olmalı.

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

  • int
  • str
  • Uygun elemanlardan oluşan tuple

Yaygın değiştirilebilir koleksiyonlar ise hashable değildir:

  • list
  • dict
  • set

Bir değerin anahtar olup olamayacağını belirleyen soru “değiştirilebilir mi?” değil, “hashable mı?” sorusudur. Değiştirilebilirlik ise birçok koleksiyonun neden hashable olmadığını anlamamıza yardım eder.

11 Liste neden anahtar olamaz?

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

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

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

Ama her tuple 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 uzun bir tür listesi ezberlemek yerine şu soruyu sormayı 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 olacak biçimde değiştirin.

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.

Her zaman en iyi olan bir veri yapısı yoktur. Sormanız gereken soru şu:

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 kolayca yapılır.
  • Gruplamada sözlük değerleri liste olabilir.
  • Anahtardan kayda hızlı ulaşmanın arkasında hash fikri vardır.
  • İki farklı anahtar aynı konuma düşebilir; buna hash çakışması denir.
  • Sözlük anahtarı ya da küme elemanı olabilmenin koşulu hashable olmaktır.
  • Bu derste hash tabanlı yapıların O(1) maliyetini ortalama durum için geçerli kabul ediyoruz.
  • Veri yapısını söz dizimine göre değil, yapılacak işlemlere göre seçeriz.

17 Kendinizi kontrol edin

  1. dict ile set arasındaki temel fark nedir?
  2. Frekans sayımını neden liste yerine sözlükle yaparız?
  3. x in some_set hangi tür problemlerde işe yarar?
  4. Hash sezgisini bir cümleyle nasıl açıklarsınız?
  5. Hash çakışması ne demektir?
  6. Sözlük anahtarı olabilmenin koşulunu neden yalnızca “immutable” sözcüğüyle açıklamak yetmez?
  7. (1, 2) hashable iken (1, [2, 3]) neden hashable değildir?
Back to top