Uygun veri yapısı ve algoritma seçimi

Bu derste öğrendiğiniz yapıların hiçbiri her iş için “en iyi” değildir. Bir kullanıcı adının alınıp alınmadığına bakmak için küme, müşterileri geliş sırasıyla işlemek için kuyruk, ürün koduyla kayda ulaşmak için sözlük uygundur. Bu hafta yeni bir veri yapısı öğrenmeyeceğiz. Bir problem için yapı seçmeyi ve seçiminizi gerekçelendirmeyi çalışacağız.

Hazır bir çözümü ya da bir AI (yapay zekâ) aracının yazdığı kodu da inceleyeceğiz. Kod çalışıyor olabilir. Yine de gereksiz bir veri yapısı seçmiş, maliyeti yanlış hesaplamış ya da algoritmanın ön koşulunu atlamış olabilir. İkili aramaya sırasız liste vermek buna bir örnektir.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • Erişim, üyelik, benzersizlik, sıra, güncelleme ve sıralama gereksinimlerini ayırt edebilmeli,
  • Problemin ne istediğine bakarak uygun Python koleksiyonunu seçebilmeli,
  • Veri yapısı seçimini üç adımlı bir karar yöntemiyle gerekçelendirebilmeli,
  • Arama yöntemini verinin sıralı olup olmadığına ve kaç kez arama yapılacağına göre seçebilmeli,
  • Elemanların hangi sırayla çıkacağına bakarak yığınla kuyruk arasında seçim yapabilmeli,
  • Bir çözümün maliyetini ölçmeden, sözle gerekçelendirebilmeli,
  • Çalışan ama gereksiz ya da yanlış yapı kullanan kodu eleştirebilmeli,
  • AI’ın yazdığı bir çözümdeki ön koşul ve maliyet hatalarını fark edebilmelisiniz.

2 Seçime problemden başlayın

Yanlış soru:

Bu problemi dict ile yapabilir miyim?

Daha iyi soru:

Program bu veriyle en sık hangi işlemleri yapacak? Bu işlemler ne kadar hızlı olmalı, ne kadar bellek kullanabilir?

Bu soruyu üç adımda cevaplayabilirsiniz.

3 Üç adımlı seçim yöntemi

3.1 1. Gerekli işlemleri belirle

Önce programın ne yapacağını açıkça yazın:

  • Sırayla dolaşma mı?
  • Anahtardan kayda erişme mi?
  • Üyelik kontrolü mü?
  • Benzersizlik mi?
  • İlk geleni önce işleme mi?
  • Son geleni önce işleme mi?
  • Sıralı rapor hazırlama mı?

3.2 2. İşlemlerin önemini ve sıklığını belirle

Bir işlem bir kez mi yapılacak, binlerce kez mi? Cevaba göre seçim değişebilir.

Örneğin:

Bir kez ürün kodu ara             → doğrusal arama yeterli olabilir
Her istekte ürün kodu ara         → dict ile indekslemek daha anlamlı olabilir

Bu kararda veri boyutunu, işlem sıklığını ve sözlüğün kullanacağı ek belleği birlikte düşünün.

3.3 3. Gereksinime en uygun yapıyı seç ve gerekçelendir

Bir yapıyı yalnızca “daha hızlı” diye seçmeyin. Yapı, problemin anlamını da korumalı: sıra önemliyse sırayı, tekrarlar önemliyse tekrarları saklamalı.

flowchart LR
    A["1. İşlemleri belirle"] --> B["2. Sıklık / maliyet gereksinimini belirle"]
    B --> C["3. Yapı veya algoritmayı seç"]
    C --> D["Seçimi doğruluk + maliyet ile gerekçelendir"]

Important

Karmaşık bir veri yapısı, karmaşık olduğu için daha iyi olmaz. Basit bir yapı işi görüyorsa çoğu zaman doğru seçim odur.

4 Temel karar ölçütleri

Gereksinim Sık kullanılan seçenek
sırayı ve tekrarları koruma list
sabit, değişmeyecek sıralı grup tuple
anahtar → değer ilişkisi dict
benzersizlik set
çok sık üyelik kontrolü çoğu zaman set / dict
son giren önce çıksın yığın: list / deque
ilk giren önce çıksın kuyruk: deque
sıralı veride çok sayıda arama ikili arama düşünülebilir
küçük veya sırasız veride basit arama doğrusal arama
kayıtları ölçüte göre düzenleme sorted() / .sort()

Bu tablo kararı sizin yerinize vermez. Veri boyutuna, verinin zaten sıralı olup olmadığına ve işlemlerin ne sıklıkla yapılacağına da bakın.

5 Senaryo 1: kullanıcı adları

Bir site, yeni bir kullanıcı kaydolurken seçilen adın daha önce alınıp alınmadığını kontrol ediyor. Adların sırası önemli değil, ama her ad yalnızca bir kez bulunmalı.

usernames = {"ada", "mert", "ece"}

if "ada" in usernames:
    print("Kullanılıyor")

Üç adımlı gerekçe:

  1. Temel işlem: üyelik kontrolü ve benzersizlik.
  2. İşlem sık yapılacak.
  3. set hem “her ad bir kez” kuralına doğrudan uyar hem de üyelik kontrolünü ortalama durumda hızlı yapar.

Liste de çalışır:

usernames = ["ada", "mert", "ece"]

Ama çok sayıda üyelik kontrolü yapılacaksa liste daha zayıf bir seçim olabilir.

6 Senaryo 2: öğrenci sırası

Bir sınıftaki öğrencilerin kayıt sırası korunacak. Aynı adı taşıyan iki öğrenci olabilir. Burada set kullanırsanız veri kaybedebilirsiniz:

Küme tekrarları sildiği için ikinci Ada kaybolur, kayıt sırası da korunmaz. “Daha hızlı” olması onu doğru yapı yapmaz.

7 Senaryo 3: ürün kodundan ürüne erişim

Ürün koduyla kayda ulaşmak, anahtarla değere ulaşmaktır. Sözlük de bu iş için vardır.

8 Senaryo 4: undo ve müşteri sırası

Elemanlar iki farklı sırayla çıkarılabilir. Metin düzenleyicideki geri al (undo) komutu en son yaptığınız değişikliği geri alır. Bankadaki sırada ise önce ilk gelen müşteriye bakılır:

Undo geçmişi      → son yapılan önce geri alınır → LIFO → yığın
Müşteri kuyruğu   → ilk gelen önce işlenir       → FIFO → kuyruk

İki durumda da elemanlar aynı türde olabilir. Yığını mı kuyruğu mu seçeceğinizi çıkarma sırası belirler.

9 Arama seçimi

Arama kararında şu soruları sorun:

  1. Veri sıralı mı?
  2. Kaç kez arama yapılacak?
  3. Aranan alana göre bir indeks (sözlük) kurulabilir mi?
  4. İndeksin kaplayacağı bellek ve kurulma süresi kabul edilebilir mi?

9.1 Bir kez arama

Sırasız küçük listede doğrusal arama yeterli olabilir.

9.2 Çok sayıda arama

Aynı anahtara göre tekrar tekrar arama yapılıyorsa iki yol mantıklı olabilir:

  • Veriden bir sözlük indeksi kurmak,
  • Veri zaten sıralıysa ikili arama kullanmak.

10 Sıralama her zaman gerekli mi?

En küçük elemanı bulmak için bütün listeyi sıralamamız gerekmez:

İki satır aynı sonucu verir, ama yapılan iş aynı değildir: min() listeyi bir kez dolaşır, sorted() ise bütün listeyi sıralar.

Yalnızca en küçük eleman gerekiyorsa bütün listeyi sıralamaya kalkmayın.

11 Karar akışı

flowchart TD
    A["Gereksinimi belirle"] --> B{"Anahtardan değere erişim?"}
    B -- Evet --> C["dict düşün"]
    B -- Hayır --> D{"Benzersizlik / sık üyelik?"}
    D -- Evet --> E["set düşün"]
    D -- Hayır --> F{"Öğe çıkarma sırası önemli mi?"}
    F -- Son giren önce --> G["yığın (stack)"]
    F -- İlk giren önce --> H["kuyruk (deque)"]
    F -- Hayır --> I{"Sıralı veride arama mı?"}
    I -- Evet --> J["ikili arama düşünülebilir"]
    I -- Hayır --> K["list + baştan sona dolaşma"]

Bu şema başlangıç için işe yarar. Gerçek programlarda birden çok yapı birlikte kullanılabilir.

12 Aynı programda birden çok yapı

Bir e-ticaret uygulamasında şu yapılar aynı anda bulunabilir:

  • Ürünlerin gösterim sırası için list,
  • Ürün kodundan erişim için dict,
  • Kullanılmış kupon kodları için set,
  • İşlenecek siparişler için deque.

Böyle bir programda tek bir veri yapısı seçilmez. Her ihtiyaç için uygun yapı seçilir ve hepsi birlikte kullanılır.

13 Çalışan ama zayıf çözüm 1

Aşağıdaki kod, bir kullanıcı adının yasaklı olup olmadığını anlamak için her sorguda listeyi baştan dolaşıyor:

Beş elemanda sorun çıkmaz. Ama yüz binlerce ad ve çok sayıda sorgu varsa set daha uygun olabilir:

blocked = {"bot1", "spam2", "fake3", "bot4", "spam5"}

Program aynı girdiye yine aynı cevabı veriyor. Yalnızca veri yapısını değiştirdik.

14 Çalışan ama zayıf çözüm 2

queue = []
queue.append("A")
queue.append("B")
current = queue.pop(0)

Bu kod FIFO kuralına uyar: ilk giren önce çıkar. Ama pop(0) her seferinde kalan elemanları birer sola kaydırır. Çok büyük ve yoğun bir kuyrukta deque.popleft() daha uygun olur.

15 Yanlış varsayım: sırasız veride ikili arama

Bir AI aracının size şu kodu önerdiğini düşünün:

def fast_search(values, target):
    low = 0
    high = len(values) - 1

    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

Fonksiyonun kendisi standart ikili aramaya benziyor. Ama kodu kullanan program ona şu listeyi veriyor:

values = [50, 3, 90, 12, 40]

Kodda söz dizimi hatası yok. Sorun ön koşulun sağlanmaması: liste sıralı değil. Liste sıralı değilse ikili aramanın “sol yarıyı at” ya da “sağ yarıyı at” kararlarına güvenilemez.

Important

AI’ın ya da bir insanın yazdığı kodu değerlendirirken yalnızca “çalışıyor mu?” diye sormayın. Hangi ön koşullar sağlanırsa doğru çalışır? sorusunu da sorun.

16 AI önerisini incelemek için kontrol listesi

Bir veri yapısı ya da algoritma önerisini şu sorularla inceleyin:

  1. Problemin ne istediği doğru anlaşılmış mı?
  2. Sıra ya da benzersizlik gerekiyorsa korunuyor mu?
  3. Algoritmanın ön koşulu sağlanıyor mu?
  4. Gereksiz sıralama, kopyalama veya dönüştürme var mı?
  5. Sık yapılan işlem için uygun koleksiyon kullanılmış mı?
  6. Boş liste, aranan değerin bulunmaması, tekrar eden değerler gibi sınır durumları düşünülmüş mü?
  7. Daha basit bir çözüm aynı işi yapabilir mi?
  8. Daha hızlı görünen çözüm fazladan bellek ya da kurulum süresi gerektiriyor mu?

17 Alıştırma: veri yapısını düzelt

Aşağıdaki kodun, yüz binlerce kayıtta çok sık üyelik kontrolü yapan bir sistemin parçası olduğunu düşünün. allowed verisini ve fonksiyonu buna göre düzenleyin. Fonksiyon aynı girdiye yine aynı sonucu vermeli.

Köşeli parantez yerine küme söz dizimini kullanın: {"python", ...}.

allowed = {"python", "data", "web", "network", "linux"}

def is_allowed(tag):
    return tag in allowed

18 Alıştırma: üç adımlı seçim gerekçesi

Bir çağrı merkezinde gelen talepler geliş sırasıyla işlenecek. Sistemde aynı anda yaklaşık 50.000 talep bekleyebilir. Her seferinde sıradaki talep kuyruğun başından alınacak.

Aşağıdaki taslağı tamamlayın:

1. Temel işlem(ler): ______________________________
2. Sıklık / maliyet gereksinimi: __________________
3. Seçim: _________________________________________
Gerekçe: __________________________________________

Gerekçenizde şunlar bulunmalı:

  • FIFO davranışı,
  • Kuyruğun başından sık sık eleman çıkarılması,
  • deque ve popleft(),
  • list.pop(0) işleminin O(n) sürmesi.

19 Gerekçelendirme dili

“set daha iyi” demek yetmez. Gerekçeniz teknik ve somut olsun:

Kullanıcı adlarının sırasını ve tekrarlarını saklamamız gerekmiyor. En sık yapılan işlem üyelik kontrolü. Bu yüzden set ihtiyacı listeden daha doğrudan karşılar ve üyelik kontrolü ortalama durumda daha ucuzdur.

Benzer şekilde:

Veri zaten sıralı ve aynı listede çok sayıda arama yapılacak. Bu yüzden O(n) süren doğrusal arama yerine O(log n) süren ikili arama uygundur.

Kısa bir gerekçe yeter. Yalnız şu üçünü içermeli: hangi işlem gerekiyor, hangi yapıyı ya da algoritmayı seçtiniz, maliyeti ne.

20 Kısa senaryo çalışması

Her senaryo için üç adımlı yöntemle bir yapı ya da algoritma seçin ve tek cümlelik bir gerekçe yazın:

  1. Son 20 hata mesajını geliş sırasına göre tutmak; yeni mesaj geldikçe en eskisi atılacak.
  2. Bir kitabın ISBN’siyle kaydına çok sık ulaşmak.
  3. Kullanılmış davet kodlarının tekrar kullanımını engellemek.
  4. Sırasız, 30 elemanlı bir listede bir değeri bir kez aramak.
  5. Sıralı 500.000 kimlik üzerinde çok sayıda arama yapmak.
  6. Her işlemde en son eklenen düzenleme adımını geri almak.

21 Bölüm özeti

  • Veri yapısı seçerken problemin ne istediğinden başlayın.
  • Seçim üç adımda yapılabilir: işlemleri belirle → sıklık/maliyet gereksinimini belirle → yapıyı seç ve gerekçelendir.
  • Daha karmaşık bir veri yapısı her zaman daha iyi değildir.
  • Sıra, benzersizlik, erişim biçimi ve çıkarma sırası problemin anlamına ait gereksinimlerdir, yalnızca hızla ilgili ayrıntılar değildir.
  • Arama yöntemi verinin sıralı olup olmamasına ve arama sıklığına bağlıdır.
  • Bir çözümün çalışması, doğru veri yapısını kullandığını göstermez.
  • Algoritmanın ön koşullarını her zaman kontrol edin.
  • AI’ın yazdığı kodu da aynı ölçütlerle değerlendirin: doğruluk, ön koşul, sınır durumları ve maliyet.

22 Kendinizi kontrol edin

  1. Veri yapısı seçiminin üç adımı nelerdir?
  2. Neden “en hızlı veri yapısı” diye tek bir doğru cevap yoktur?
  3. set problemin hangi gereksinimlerini doğrudan karşılar?
  4. Çok sık kimlik araması için dict indeksi ne kazandırır ve ne tür ek maliyet getirir?
  5. Kuyruk olarak kullanıldığında deque ile normal liste arasındaki temel maliyet farkı nedir?
  6. Size ikili arama önerildiğinde hangi ön koşulu mutlaka kontrol etmelisiniz?
  7. AI’ın yazdığı bir çözümü incelerken çıktının doğru çıkması neden yetmez?
Back to top