Veri yapıları, ADT ve maliyet sezgisi

Programlama Temelleri dersinde bir problemi Python koduna dönüştürmeyi öğrendiniz. Bu derste bir adım daha ileri gideceğiz: Aynı problemi çözen farklı programlar arasından hangisini neden seçmeliyiz?

Bir program yalnızca doğru sonuç üretmekle kalmaz; veriyi belirli bir biçimde düzenler ve o veri üzerinde belirli işlemleri tekrar tekrar gerçekleştirir. Veri yapıları ve algoritmalar, bu iki kararı sistematik biçimde düşünmemizi sağlar.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • veri yapısı, algoritma ve soyut veri türü (ADT) kavramlarını birbirinden ayırabilmeli,
  • aynı veriyi list, set ve dict ile temsil etmenin farklı amaçlara hizmet ettiğini açıklayabilmeli,
  • bir veri yapısını seçerken yapılacak işlemleri düşünmeniz gerektiğini fark edebilmeli,
  • O(1), O(n) ve O(n²) ifadelerini matematiksel ispat yapmadan sezgisel düzeyde yorumlayabilmeli,
  • küçük deneylerde işlem sayısı ile çalışma süresi arasındaki ilişkiyi gözlemleyebilmeli,
  • iki doğru çözüm arasında kısa bir seçim gerekçesi yazabilmelisiniz.

2 Problem: aynı veriyi nasıl tutalım?

Bir kulübe kayıtlı öğrencilerin numaralarını düşünelim:

101, 107, 112, 118, 125

İlk akla gelen çözüm bir liste olabilir:

uyeler = [101, 107, 112, 118, 125]

Bu yanlış değildir. Fakat gerçek ihtiyaç şu ise karar değişebilir:

Sisteme gelen bir öğrenci numarasının kulüp üyesi olup olmadığını çok sık kontrol edeceğiz.

Aynı numaraları bir kümede de tutabiliriz:

uyeler = {101, 107, 112, 118, 125}

İki yapı da numaraları saklar. Buna rağmen aynı problem için eşit derecede uygun olmak zorunda değildirler.

NoteVeri yapısı seçimi sözdizimi seçimi değildir

Bu derste list, dict, set gibi yapıların nasıl yazıldığını zaten bildiğinizi varsayıyoruz. Asıl sorumuz şudur: Hangi işlem için hangi yapı daha uygun?

3 Veri yapısı nedir?

Bir veri yapısı (data structure), verinin program içinde nasıl düzenlendiğini ve bu veri üzerinde hangi işlemlerin nasıl gerçekleştirileceğini belirleyen yapıdır.

Örneğin:

  • list: sıralı bir eleman dizisi,
  • dict: anahtar-değer eşlemeleri,
  • set: benzersiz değerler topluluğu,
  • deque: iki uçtan verimli ekleme ve çıkarma yapılabilen yapı.

Veri yapısı seçimi, programın davranışını etkiler. Bazı yapılar sırayı korumaya, bazıları anahtarla erişime, bazıları ise üyelik sorgusuna daha uygundur.

4 Algoritma nedir?

Bir algoritma (algorithm), belirli bir problemi çözmek için izlenen sonlu ve açık adımlar dizisidir.

Örneğin bir listede 42 değerini bulmak için şu algoritmayı kullanabiliriz:

  1. İlk elemana bak.
  2. Aranan değerle karşılaştır.
  3. Eşitse dur.
  4. Değilse sonraki elemana geç.
  5. Liste biterse değer bulunamadı de.

Bu yaklaşım doğrusal arama (linear search) fikridir. Yedinci haftada ayrıntılı olarak işleyeceğiz.

Şimdilik önemli ayrım şudur:

flowchart LR
    P[Problem] --> D[Veriyi düzenleme kararı]
    P --> A[İşlem adımları kararı]
    D --> DS[Veri yapısı]
    A --> AL[Algoritma]
    DS --> C[Çalışan çözüm]
    AL --> C

Veri yapısı verinin düzenlenişine, algoritma ise işlemin adımlarına odaklanır. Gerçek programlarda ikisi birlikte çalışır.

5 Soyut veri türü: önce davranışı düşünmek

Soyut veri türü (Abstract Data Type, ADT), bir yapının içeride tam olarak nasıl gerçekleştirildiğinden önce hangi işlemleri sunduğunu ve bu işlemlerin ne anlama geldiğini tanımlar.

Bir yığını düşünelim. Yığın için şu davranışları isteyebiliriz:

  • en üste eleman eklemek,
  • en üstteki elemanı çıkarmak,
  • en üstteki elemana bakmak,
  • yapının boş olup olmadığını sormak.

Burada henüz list mi, deque mu, yoksa başka bir yapı mı kullanacağımıza karar vermedik.

flowchart TD
    S[Yığın / Stack ADT]
    S --> P[push: üste ekle]
    S --> O[pop: üstten çıkar]
    S --> K[peek: üsttekine bak]
    S --> E[is_empty: boş mu?]

ADT bize ne yapılacağını söyler; gerçekleştirim ise bunun nasıl yapılacağını belirler.

ImportantBu derste sınıf yazmak ön koşul değildir

Yığın ve kuyruk gibi ADT’leri öğrenirken kendi Stack veya Queue sınıflarımızı yazmayacağız. Bu yapıları Python’ın list ve collections.deque gibi hazır araçlarıyla gerçekleştireceğiz. Kullanıcı tanımlı sınıflar Nesne Tabanlı Programlama I dersinin konusudur.

6 Aynı veri, üç farklı yapı

Aşağıdaki kod aynı öğrenci adlarını üç farklı koleksiyonda tutuyor. Çalıştırmadan önce çıktıyı tahmin edin.

#| edit: false
#| completion: false
ogrenci_listesi = ["Ali", "Ayşe", "Zeynep", "Ali"]
ogrenci_kumesi = {"Ali", "Ayşe", "Zeynep", "Ali"}
ogrenci_sozlugu = {
    101: "Ali",
    102: "Ayşe",
    103: "Zeynep",
}

print("Liste:", ogrenci_listesi)
print("Listedeki eleman sayısı:", len(ogrenci_listesi))
print("Kümedeki eleman sayısı:", len(ogrenci_kumesi))
print("102 numaralı öğrenci:", ogrenci_sozlugu[102])

Burada üç farklı gereksinim görünür hâle gelir:

Gereksinim Uygun aday
Sıralı değerleri ve tekrarları korumak list
Benzersiz değerleri tutmak, üyelik sorgulamak set
Bir anahtarı bir değerle eşlemek dict

Bu tablo mutlak bir reçete değildir; ancak veri yapısı seçimini işlem gereksiniminden başlatmak için iyi bir ilk adımdır.

7 Alıştırma — uygun yapıyı seçin

Bir sistemde yalnızca daha önce kullanılmış kullanıcı adlarını tutacağız. Amaç, yeni kayıt sırasında bir kullanıcı adının daha önce alınıp alınmadığını sık sık kontrol etmek.

Aşağıdaki veriler değişkenini bu ihtiyaca uygun bir koleksiyonla doldurun ve "deniz" değerinin yapıda olup olmadığını yazdırın.

#| exercise: hafta01-yapi-secimi
#| completion: false
#| persist: true
veriler = ______

print("deniz" in veriler)
#| exercise: hafta01-yapi-secimi
#| check: true
import ast

try:
    tree = ast.parse(user_code)
    set_nodes = [n for n in ast.walk(tree) if isinstance(n, ast.Set)]
    set_calls = [
        n for n in ast.walk(tree)
        if isinstance(n, ast.Call)
        and isinstance(n.func, ast.Name)
        and n.func.id == "set"
    ]
    has_membership = any(isinstance(n, ast.Compare) and any(isinstance(op, ast.In) for op in n.ops) for n in ast.walk(tree))
    correct = bool(set_nodes or set_calls) and has_membership
except SyntaxError:
    correct = False

feedback = (
    {"correct": True, "message": "Küme ve üyelik sorgusu bu gereksinim için uygun bir seçim."}
    if correct
    else {"correct": False, "message": "Benzersizlik ve sık üyelik sorgusu için set kullanmayı düşünün."}
)
feedback

{"ali", "deniz", "zeynep"} gibi bir küme oluşturabilirsiniz.

Solution. 

veriler = {"ali", "deniz", "zeynep"}
print("deniz" in veriler)

8 Bir çözümün maliyeti ne demektir?

İki algoritma aynı doğru sonucu verebilir, fakat farklı miktarda iş yapabilir.

Örneğin bir listede belirli bir değeri aradığımızı düşünelim. Aranan değer ilk sıradaysa hemen bulabiliriz; son sıradaysa neredeyse bütün elemanlara bakmamız gerekir.

Veri büyüdükçe kaç adım yapıldığı önem kazanmaya başlar.

Bu derste maliyeti iki açıdan düşüneceğiz:

  • zaman maliyeti: yaklaşık ne kadar iş yapılıyor?
  • bellek maliyeti: çözüm ne kadar ek veri tutuyor?

Dersin büyük kısmında zaman maliyetine odaklanacağız.

9 Big-O: büyüme davranışını anlatan kısa dil

Big-O gösterimi, veri boyutu büyürken yapılan işin nasıl büyüdüğünü ifade etmek için kullanılan bir dildir.

Bu derste Big-O’yu matematiksel ispatlarla değil, işlem sayısı ve gözlem üzerinden kullanacağız.

9.1 O(1): veri büyüse de iş yaklaşık sabit

Bir listenin belirli indeksindeki elemana erişelim:

#| edit: false
#| completion: false
sayilar = [10, 20, 30, 40, 50]
print(sayilar[3])

Listenin 5 ya da 50.000 elemanlı olması, sayilar[3] gibi doğrudan indeks erişimini aynı türden bir iş olmaktan çıkarmaz. Bu tür davranışı sezgisel olarak O(1) ile ifade ederiz.

9.2 O(n): veri iki katına çıkınca iş de yaklaşık iki katına çıkabilir

Aşağıdaki fonksiyon listedeki her elemana bir kez bakar:

#| edit: false
#| completion: false
def sayi_var_mi(veriler, aranan):
    kontrol = 0
    for deger in veriler:
        kontrol += 1
        if deger == aranan:
            return True, kontrol
    return False, kontrol

for boyut in [10, 100, 1000]:
    veriler = list(range(boyut))
    bulundu, kontrol = sayi_var_mi(veriler, -1)
    print(f"n={boyut:4} -> {kontrol} kontrol")

Aranan değer listede olmadığı için bütün elemanlar kontrol edilir. n büyüdükçe kontrol sayısı da yaklaşık n kadar büyür. Bu davranışı O(n) diye adlandırırız.

9.3 O(n²): her eleman için tekrar bütün elemanlara bakmak

Şu fonksiyon her elemanı diğer bütün elemanlarla karşılaştırır:

#| edit: false
#| completion: false
def karsilastirma_sayisi(n):
    sayac = 0
    for i in range(n):
        for j in range(n):
            sayac += 1
    return sayac

for boyut in [10, 20, 40, 80]:
    print(boyut, karsilastirma_sayisi(boyut))

n iki katına çıktığında iş yaklaşık dört katına çıkar. Bu tür büyüme O(n²) ile ifade edilir.

10 Büyüme farkını tabloyla görelim

Aşağıdaki değerler gerçek çalışma süresi değildir; yalnızca büyüme biçimini karşılaştıran işlem sayılarıdır.

n O(1) O(n) O(n²)
10 1 10 100
100 1 100 10.000
1.000 1 1.000 1.000.000
10.000 1 10.000 100.000.000
WarningBig-O kronometre sonucu değildir

O(n) ifadesi “bu program 1 saniyede çalışır” anlamına gelmez. Bilgisayar, Python sürümü, veri türü ve uygulama ayrıntıları gerçek süreyi etkiler. Big-O, temel olarak veri büyüdükçe işin nasıl büyüdüğünü anlatır.

11 Önce işlem say, sonra zaman ölç

İlk haftalarda performansı anlamanın en güvenli yolu doğrudan milisaniyelere bakmak yerine yapılan işlemleri saymaktır.

Aşağıdaki örneği çalıştırın:

#| edit: false
#| completion: false
def ara(veriler, aranan):
    adim = 0
    for deger in veriler:
        adim += 1
        if deger == aranan:
            return adim
    return adim

veriler = list(range(20))

print("İlk eleman:", ara(veriler, 0), "adım")
print("Orta eleman:", ara(veriler, 10), "adım")
print("Son eleman:", ara(veriler, 19), "adım")
print("Bulunamayan:", ara(veriler, 100), "adım")

Aynı algoritmanın yaptığı iş, girdinin yalnızca boyutuna değil aranan değerin konumuna da bağlı olabilir. Big-O çoğu zaman veri büyürken önemli olan üst düzey davranışı özetler.

12 Liste ve kümede üyelik: aynı sonuç, farklı yapı

Şimdi aynı üyelik sorusunu iki farklı yapıda soralım:

#| edit: false
#| completion: false
liste = list(range(20))
kume = set(range(20))

print(19 in liste)
print(19 in kume)

İki sonuç da True olur. Farkı görmek için veri yapısının çalışma biçimini düşünmeliyiz:

  • listede genel üyelik araması elemanları sırayla kontrol edebilir → O(n) sezgisi,
  • kümede hash tabanlı üyelik sorgusu ortalama durumda sabit zamana yakın davranabilir → O(1) sezgisi.

Buradaki “ortalama durumda” ifadesi önemlidir. Hash tablolarının ayrıntılarını üçüncü haftada ele alacağız.

13 Zaman ölçümü yaparken dikkat

Tarayıcı içindeki Python ortamında küçük zaman farkları kararsız olabilir. Yine de daha büyük veri üzerinde kaba bir karşılaştırma yapabiliriz.

#| edit: false
#| completion: false
import time

boyut = 200_000
liste = list(range(boyut))
kume = set(range(boyut))
aranan = -1

baslangic = time.perf_counter()
for _ in range(100):
    aranan in liste
liste_sure = time.perf_counter() - baslangic

baslangic = time.perf_counter()
for _ in range(100):
    aranan in kume
kume_sure = time.perf_counter() - baslangic

print("Liste:", round(liste_sure, 6), "saniye")
print("Küme :", round(kume_sure, 6), "saniye")

Sonuçların bilgisayardan bilgisayara değişmesi normaldir. Buradaki amaç kesin bir saniye değeri ezberlemek değil, aynı işlemin yapı seçimine bağlı olarak farklı maliyet gösterebildiğini görmektir.

14 Alıştırma — büyüme davranışını tanıyın

Aşağıdaki fonksiyonun kaç kez sayac += 1 çalıştırdığını farklı n değerleri için gözlemleyin. Sonra n iki katına çıktığında sayacın nasıl değiştiğini açıklayın.

#| exercise: hafta01-buyume
#| completion: false
#| persist: true
def islem_sayisi(n):
    sayac = 0
    for i in range(n):
        for j in range(n):
            sayac += 1
    return sayac

for n in [5, 10, 20, 40]:
    print(n, islem_sayisi(n))

# Aşağıya kısa yorumunuzu yazabilirsiniz.

Bu örnekte n iki katına çıktığında işlem sayısının yaklaşık dört katına çıktığını görmelisiniz. Bu nedenle büyüme O(n²) olarak ifade edilir.

15 Alıştırma — iki doğru çözümden birini seçin

Bir uygulama, 100.000 ürün kodunun bulunduğu bir koleksiyonda aynı ürün kodunun daha önce eklenip eklenmediğini sürekli kontrol ediyor. Sıra önemli değil ve her kod yalnızca bir kez tutulmalı.

Aşağıdaki seçeneklerden hangisi daha uygun adaydır?

urunler = []

veya

urunler = set()

Yanıtınızda yalnızca “set daha hızlıdır” demek yerine şu iki noktayı birlikte kullanın:

  1. problem gereksinimi,
  2. yapılacak temel işlem.
Tip

İyi bir teknik gerekçe şu kalıba yaklaşır: “Bu problemde X gerekiyor ve en sık Y işlemi yapılıyor; bu nedenle Z yapısı daha uygun.”

16 Yanlış düşünce: “en hızlı veri yapısını seçelim”

Tek bir veri yapısı her işlemde en iyi değildir. Örneğin küme üyelik sorgusu için çok uygun olabilir; fakat elemanları belirli bir sırada tutmak ya da indeksle üçüncü elemana erişmek istiyorsak problem değişir.

Dolayısıyla doğru soru:

En hızlı veri yapısı hangisi?

olmak yerine:

Bu problemde hangi işlemler önemli ve hangi yapı bu işlemleri uygun biçimde destekliyor?

olmalıdır.

17 Karar akışı

İlk haftalarda yapı seçerken aşağıdaki basit düşünme akışını kullanabilirsiniz:

flowchart TD
    A[Veri hakkında neye ihtiyacım var?]
    A --> B{Anahtar-değer ilişkisi var mı?}
    B -- Evet --> D[dict düşün]
    B -- Hayır --> C{Benzersizlik ve üyelik mi önemli?}
    C -- Evet --> S[set düşün]
    C -- Hayır --> E{Sıra ve indeks önemli mi?}
    E -- Evet --> L[list düşün]
    E -- Hayır --> F[İşlemleri yeniden belirle]

Bu şema ilerleyen haftalarda deque, yığın, kuyruk ve farklı algoritmalarla genişleyecek.

18 Kendinizi kontrol edin

  1. Veri yapısı ile algoritma arasındaki temel fark nedir?
  2. ADT neden bir Python sınıfıyla aynı şey değildir?
  3. list ve set aynı veriyi tutabilse bile neden farklı problemler için tercih edilebilir?
  4. O(1), O(n) ve O(n²) büyümelerini kendi cümlelerinizle açıklayın.
  5. n iki katına çıktığında O(n²) davranışındaki işlem sayısı yaklaşık neden dört katına çıkar?
  6. “Kod çalışıyor” ifadesi neden veri yapısı seçimimizi değerlendirmek için yeterli değildir?

19 Bölüm sonu uygulaması — gereksinimden yapıya

Aşağıdaki üç senaryo için önce uygun Python yapısını seçin; sonra seçiminizi birer cümleyle gerekçelendirin.

Senaryo A — Otobüs bekleme sırası
Yolcular geliş sırasına göre hizmet alacak.

Senaryo B — Kullanılmış kupon kodları
Bir kodun daha önce kullanılıp kullanılmadığı çok sık sorgulanacak ve tekrar tutulmayacak.

Senaryo C — Öğrenci kaydı
Öğrenci numarasından öğrencinin adına ve notuna erişilecek.

Henüz kuyruk yapısını ayrıntılı görmediğimiz için Senaryo A’da list aklınıza gelebilir. Altıncı haftada aynı problemi deque ile tekrar ele alacak ve iki yaklaşımın maliyetini karşılaştıracağız.

20 Bu haftadan aklınızda kalsın

Important

Veri yapısı seçimi, verinin görünüşüne göre değil yapılacak işlemlere göre yapılır.
Big-O ise “hangi kod daha hızlı?” sorusuna tek bir saniye değeri vermek yerine, veri büyüdükçe yapılan işin nasıl büyüdüğünü anlatan ortak bir dildir.

Back to top