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 sonuca ulaşırken veriyi belli bir biçimde tutar ve o veri üzerinde bazı işlemleri tekrar tekrar yapar. Veriyi nasıl düzenleyeceğimiz ve hangi adımlarla işleyeceğimiz iki ayrı karardır. Bu derste iki kararı da bilerek vermeyi öğreneceğiz: ilki veri yapısını, ikincisi algoritmayı belirler.

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 ya da dict ile tutmanın hangi amaca uyduğunu açıklayabilmeli,
  • Veri yapısı seçerken önce üzerinde yapılacak işlemlere bakmanız 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,
  • İki 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ğil. Ama ihtiyacımız şuysa 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. Yine de bu problem için ikisi aynı ölçüde uygun olmayabilir.

NoteYazımı biliyoruz, seçimi öğreneceğiz

list, dict, set gibi yapıların nasıl yazıldığını Programlama Temelleri’nden biliyorsunuz. Bu derste şu soruyu soracağız: 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 yapılacağını belirler.

Ö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ı.

Seçtiğiniz veri yapısı programın nasıl çalışacağını etkiler. Bazı yapılar sırayı korumaya, bazıları anahtarla erişime, bazıları da üyelik sorgusuna (bir değerin yapıda olup olmadığını sormaya) 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ın adı doğrusal arama (linear search). Yedinci haftada ayrıntılı işleyeceğiz.

Şimdilik şu ayrımı aklınızda tutun:

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 nasıl düzenlendiğini, algoritma işin hangi adımlarla yapılacağını anlatır. Çalışan bir programda ikisi birlikte bulunur.

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

Soyut veri türü (Abstract Data Type, ADT), bir yapının içeride nasıl kodlandığına girmeden hangi işlemlere izin verdiğini ve bu işlemlerin ne yaptığını tanımlar.

Bir yığın (stack) düşünelim: üst üste konmuş tabaklar gibi, eklemeyi de almayı da yalnız en üstten yaptığımız bir yapı. Yığından ş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 ne yapılacağını söyler. Gerçekleştirim (implementation), yani ADT’nin kodla yazılmış hâli, bunun nasıl yapılacağını belirler.

ImportantBu derste sınıf yazmayacağız

Yığın ve kuyruk (queue) gibi ADT’ler için kendi Stack ya da Queue sınıflarımızı yazmayacağız. Bu yapıları Python’ın hazır araçlarıyla, yani list ve collections.deque ile 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.

Bu örnek üç farklı ihtiyacı gösteriyor:

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 her durumda işe yarayan bir reçete değil. Yine de yapı seçerken hangi işlemlere ihtiyaç olduğunu sormak için iyi bir başlangıç.

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

Bir sistemde yalnızca daha önce kullanılmış kullanıcı adlarını tutacağız. 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 edeceğiz.

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.

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

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 gerektiği önem kazanır.

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 büyüdükçe yapılan işin nasıl arttığını birkaç harfle anlatır: O(1), O(n), O(n²) gibi. Buradaki n verideki eleman sayısıdır.

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

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

Bir listenin belirli indeksindeki elemana erişelim:

Liste 5 elemanlı da olsa 50.000 elemanlı da olsa sayilar[3] gibi doğrudan indeks erişimi aynı türden bir iştir. Bu davranışı O(1) diye gösteririz.

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:

Aranan değer listede olmadığı için bütün elemanlara bakılır: n eleman için n kontrol. Bu davranışa O(n) denir.

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:

n iki katına çıktığında iş yaklaşık dört katına çıkar. Bu büyümenin adı O(n²).

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

Tablodaki sayılar çalışma süresi değil, işlem sayısıdır. Yalnızca büyüme biçimlerini karşılaştırmak için verildi.

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 gerçekleştirimin ayrıntıları gerçek süreyi etkiler. Big-O yalnızca 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ı anlamak için milisaniyelere bakmak yerine yapılan işlemleri saymak daha güvenilirdir.

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

Aynı algoritmanın yaptığı iş yalnızca girdinin boyutuna değil, aranan değerin nerede durduğuna da bağlı olabilir. Big-O ise çoğu zaman veri büyüdükçe öne çıkan genel davranışı özetler.

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

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

İki sonuç da True olur. Fark, iki yapının içeride nasıl çalıştığındadır:

  • Liste, in sorusunu cevaplamak için elemanlara sırayla bakar → O(n) sezgisi,
  • Küme hash tabanlıdır: değere bakarak onu nerede arayacağını hesaplar. Bu yüzden üyelik sorgusu ortalama durumda sabit zamana yakın çalışır → O(1) sezgisi.

“Ortalama durumda” kaydını atlamayın. Nedenini hash tablolarını işlediğimiz üçüncü haftada göreceğiz.

13 Zaman ölçümü yaparken dikkat

Tarayıcıda çalışan Python’da küçük zaman farkları her çalıştırmada değişebilir. Yine de büyük bir veriyle kaba bir karşılaştırma yapabiliriz.

Sonuçların bilgisayardan bilgisayara değişmesi normal. Burada bir saniye değeri ezberlemiyoruz; aynı işlemin maliyetinin seçilen yapıya göre değişebildiğini görüyoruz.

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

Aşağıdaki fonksiyon farklı n değerleri için sayac += 1 satırını kaç kez çalıştırıyor? Çıktıya bakın. Sonra n iki katına çıktığında sayacın nasıl değiştiğini açıklayın.

n iki katına çıktığında işlem sayısının yaklaşık dört katına çıktığını görmelisiniz. Bu yüzden büyüme O(n²)’dir.

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

Bir uygulamada 100.000 ürün kodu var. Uygulama, gelen bir kodun 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 iki seçenekten hangisi daha uygun?

urunler = []

veya

urunler = set()

Yanıtınızda yalnızca “set daha hızlı” demeyin. Gerekçenizi şu iki noktaya birlikte dayandırın:

  1. Problemin ne istediği,
  2. En sık yapılacak işlem.
Tip

İyi bir gerekçe aşağı yukarı şöyle kurulur: “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”

Hiçbir veri yapısı her işlemde en iyisi değildir. Örneğin küme üyelik sorgusu için çok uygundur; ama elemanları belli bir sırada tutmak ya da indeksle üçüncü elemana erişmek istiyorsak küme bu işleri yapamaz.

Bu yüzden şunu sormak yerine:

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

şunu sormalıyız:

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

17 Karar akışı

İlk haftalarda yapı seçerken aşağıdaki basit akışı izleyebilirsiniz:

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

İlerleyen haftalarda bu şemaya deque, yığın, kuyruk ve yeni algoritmalar eklenecek.

18 Kendinizi kontrol edin

  1. Veri yapısı ile algoritma arasındaki temel fark nedir?
  2. ADT ile bir Python sınıfı arasındaki fark nedir?
  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. Kodun çalışması, seçtiğimiz veri yapısının iyi bir seçim olduğunu göstermeye neden yetmez?

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 yeniden çözecek ve iki yaklaşımın maliyetini karşılaştıracağız.

20 Bu haftadan aklınızda kalsın

Important

Veri yapısını, verinin neye benzediğine göre değil, üzerinde yapılacak işlemlere göre seçin.
Big-O, “hangi kod daha hızlı?” sorusuna saniye cinsinden cevap vermez. Veri büyüdükçe yapılan işin nasıl büyüdüğünü anlatır.

Back to top