Bütünleştirme ve final hazırlığı

Bu hafta yeni veri yapısı veya yeni algoritma öğrenmeyeceğiz. Amaç, dönem boyunca öğrendiğimiz kavramları tek bir problem üzerinde birlikte kullanmak ve hangi kararı neden verdiğimizi açıklamaktır.

Bu bölümde küçük bir kütüphane kayıt sistemi üzerinden şu becerileri birleştireceğiz:

Bölümün sonunda ise farklı bir bağlama geçerek transfer görevi yapacağız. Böylece yalnızca kütüphane örneğini ezberleyip ezberlemediğinizi değil, aynı düşünme biçimini yeni bir probleme taşıyıp taşıyamadığınızı sınayacağız.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • Bir problem metninden veri ve işlem gereksinimlerini çıkarabilmeli,
  • Birden çok koleksiyonu birlikte kullanabilmeli,
  • Hazır kod tabanında sınırlı bir değişiklik yapabilmeli,
  • Arama ve sıralama yöntemlerini uygun bağlamda seçebilmeli,
  • Sınır durumlarını assert ile doğrulayabilmeli,
  • Çözümünüzü veri yapısı ve maliyet açısından kısa biçimde gerekçelendirebilmeli,
  • Aynı karar yöntemini daha önce görmediğiniz yeni bir problem bağlamına aktarabilmelisiniz.

2 Problem: küçük kütüphane sistemi

Sistemde kitaplar şu alanlara sahiptir:

  • id
  • title
  • category
  • available

Ayrıca öğrenciler ödünç almak istedikleri kitaplar için bekleme sırasına girebilir.

Başlangıç verisi:

3 1. Gereksinimleri ayıralım

Sistem şu işlemleri yapacak:

  1. Bütün kitapları sırayla göstermek,
  2. Kitap kimliğine göre sık erişim yapmak,
  3. Belirli kategorideki kitapları filtrelemek,
  4. Başlığa göre sıralı rapor üretmek,
  5. Ödünçteki kitap için öğrencileri geliş sırasıyla bekletmek.

Tek bir veri yapısı bütün gereksinimler için en iyi değildir.

Gereksinim Uygun yapı / yaklaşım
kitapların genel listesi list
kimliğe göre erişim dict indeks
kategori filtresi doğrusal dolaşma
başlığa göre rapor sorted(..., key=...)
bekleme sırası deque

Bu tablo, dönem boyunca vurguladığımız gereksinim → seçim ilişkisini gösterir.

4 2. Kimliğe göre indeks oluşturma

Bu indeks, aynı liste üzerinde kimliğe göre tekrar tekrar doğrusal arama yapma ihtiyacını azaltır.

5 3. Kategoriye göre filtreleme

Bu işlem bütün kayıtları görebilmek zorunda olduğu için doğrusal dolaşma doğaldır.

6 4. Sıralı rapor

sorted() kullandığımız için orijinal books listesinin sırası değişmez.

7 5. Bekleme sırası

Bir kitap ödünçteyse öğrenciler FIFO sırasıyla beklesin:

Bu problem yığın değil kuyruk davranışı ister; ilk gelen öğrencinin önce hizmet alması gerekir.

8 6. Aynı verinin birden çok görünümü

Bir kitabın aynı sözlük nesnesi hem books listesinde hem books_by_id sözlüğünde tutulabilir:

Neden iki yerde de değişiklik görünür? Çünkü iki koleksiyon aynı kitap sözlüğüne referans verir.

Bu davranış bazen yararlıdır; bazen bağımsız kopya bekleyen programcı için hata kaynağı olabilir. Referans sezgisini unutmayın.

9 7. Hazır kod tabanına özellik ekleme

Aşağıdaki kod küçük bir başlangıç sistemidir:

Şimdi buna “kitap iade edildiğinde sıradaki öğrenciye ver” özelliği ekleyeceğiz.

10 Alıştırma — return_book fonksiyonu

Kurallar:

  1. Kitap kimliği yoksa None döndür,
  2. Bekleme listesinde öğrenci varsa ilk öğrenciyi çıkar ve adını döndür,
  3. Bekleyen yoksa kitabı available = True yap ve None döndür,
  4. Bekleyen öğrenciye kitap verildiğinde kitap kullanılabilir (available=True) olmamalıdır.

book = books_by_id.get(book_id) ile başlayın. if book is None: return None. Sonra waiting_lists[book_id] kuyruğunu kontrol edin.

def return_book(book_id):
    book = books_by_id.get(book_id)
    if book is None:
        return None

    queue = waiting_lists[book_id]

    if queue:
        book["available"] = False
        return queue.popleft()

    book["available"] = True
    return None

11 8. Davranışı doğrulama

Yeni özelliği yalnızca bir örnekle denemek yeterli değildir. Sınır durumlarını da kontrol edin:

Bu testler üç önemli durumu kapsar:

  • Bekleyen var,
  • Bekleyen yok,
  • Kitap yok.

12 9. Kısa maliyet yorumu

Bu sistem için birkaç temel işlem:

12.1 Kimliğe göre kitap bulma

books_by_id.get(book_id) sözlük erişimidir. Ortalama durumda O(1) sezgisiyle düşünürüz.

12.2 Kategoriye göre bütün kitapları bulma

Tüm books listesini dolaşmak gerekir: O(n).

12.3 Bekleme listesinden sıradaki öğrenciyi alma

deque.popleft() kuyruk için uygun ve yaklaşık O(1) davranışlı işlemdir.

12.4 Başlığa göre rapor sıralama

sorted() genel amaçlı verimli bir sıralama aracıdır; sıralamanın maliyeti veri boyutuyla birlikte doğrusalın üzerinde büyür. Bu derste yerleşik sıralamayı uygulamada tercih ederiz.

13 10. Mini karar tablosu

Aşağıdaki tabloyu kapatıp her satırın cevabını kendiniz üretmeye çalışın:

İhtiyaç Seçim Kısa gerekçe
kimliğe göre sık erişim dict anahtar tabanlı erişim
benzersiz üye numaraları set benzersizlik + üyelik
son yapılan işlemi geri al yığın LIFO
gelen talepleri sırayla işle deque FIFO
sırasız küçük veride bir kez ara doğrusal arama sıralama maliyetine gerek yok
sıralı büyük veride çok kez ara ikili arama O(log n) arama sezgisi

14 11. Transfer görevi — destek talepleri sistemi

Şimdi kütüphane örneğini bırakıyoruz. Aşağıdaki problem bu kitapta daha önce bütünleşik biçimde çözülmedi.

Bir teknik destek sistemi şu gereksinimlere sahip:

  1. Her talebin benzersiz bir ticket_id değeri var.
  2. Talepler geldikleri sırayla işlenecek.
  3. ticket_id ile belirli bir talebe çok sık erişilecek.
  4. Daha önce kapatılmış kimliklerin yeniden kullanılmasına izin verilmeyecek.
  5. Yönetici, açık talepleri öncelik puanına göre sıralı rapor olarak görmek isteyecek.
  6. Son yapılan yönetim değişikliğinin geri alınabilmesi istenecek.

14.1 Görev A — yapı seçimi

Her gereksinim için uygun yapı veya yaklaşımı seçin:

Açık taleplerin geliş sırası: ______________________
Ticket ID ile erişim: ______________________________
Kapatılmış kimlikler: ______________________________
Öncelik raporu: ____________________________________
Geri alma geçmişi: _________________________________

14.2 Görev B — üç adımlı gerekçe

  1. Haftadaki yöntemi kullanarak ticket ID ile erişim için kısa gerekçe yazın:
1. Temel işlem: ____________________________________
2. Sıklık / maliyet: _______________________________
3. Seçim: __________________________________________
Gerekçe: ___________________________________________

14.3 Görev C — yanlış çözümü eleştirin

Bir AI aracı şu çözümü öneriyor:

open_tickets = []

# yeni talep
open_tickets.append(ticket)

# sıradaki talep
current = open_tickets.pop(0)

Bu kod FIFO açısından çalışabilir. Ancak on binlerce talebin bulunduğu yoğun bir sistemde hangi satırı neden sorgularsınız? Daha uygun Python yapısı nedir?

14.4 Görev D — arama kararı

Açık talepler ticket_id değerine göre sıralı tutulmuyor. Buna rağmen bir öğrenci ikili arama kullanmayı öneriyor. Bu önerideki temel ön koşul hatasını açıklayın.

Important

Transfer görevinin amacı belirli bir kodu ezberlemek değildir. Beklenen düşünme sırası şudur:

gereksinimi çıkar → temel işlemi belirle → uygun yapı/algoritmayı seç → ön koşulu kontrol et → maliyeti kısa gerekçelendir

15 Final için kendinizi kontrol edin

Aşağıdaki soruların her birine birkaç cümleyle yanıt verebiliyorsanız dersin ana omurgasını büyük ölçüde kurmuşsunuz demektir:

  1. list, dict ve set hangi gereksinimlerde birbirinden ayrılır?
  2. Aliasing ile sığ kopya arasındaki fark nedir?
  3. Yığın ile kuyruğun çıkarma sırası nasıl farklıdır?
  4. deque.popleft() neden list.pop(0) yerine tercih edilebilir?
  5. Doğrusal arama ve ikili arama hangi ön koşullarda uygundur?
  6. Insertion sort’un sıralı ve ters sıralı girdide davranışı neden farklıdır?
  7. sorted() ile .sort() arasındaki fark nedir?
  8. O(1), O(log n), O(n), O(n log n) ve O(n²) büyümelerini sezgisel olarak açıklayabilir misiniz?
  9. Bir veri yapısını seçerken hangi üç adımı izlemelisiniz?
  10. Çalışan bir çözümün neden yine de zayıf bir veri yapısı seçimi olabileceğini açıklayabilir misiniz?

16 Bölüm özeti

  • Gerçek problemler çoğu zaman birden çok veri yapısını birlikte gerektirir.
  • list, dict, set ve deque farklı işlem gereksinimlerine hizmet eder.
  • Bir indeks oluşturmak, tekrar eden aramalarda önemli avantaj sağlayabilir.
  • Referans ilişkileri, aynı kaydın birden fazla yapıdan görülmesini sağlayabilir.
  • Sınır durumlarını assert ile doğrulamak çözümün güvenilirliğini artırır.
  • Finalde yalnızca kod üretmek değil, neden bu yapı ve neden bu algoritma? sorusunu yanıtlamak önemlidir.
  • Transfer görevi, aynı düşünme modelini daha önce görülmemiş bir bağlama taşıyabilmeyi ölçer.
Back to top