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

Bu hafta yeni bir veri yapısı ya da algoritma öğrenmeyeceğiz. Dönem boyunca öğrendiklerimizi tek bir problemde birlikte kullanacak ve her kararın gerekçesini açıklayacağız.

Problemimiz küçük bir kütüphane kayıt sistemi. Bu sistemi yazarken şunları bir arada kullanacağız:

Bölümün sonunda bir transfer görevi var: aynı düşünme biçimini kütüphaneyle ilgisi olmayan bir probleme, bir teknik destek sistemine uygulayacaksınız. Böylece kütüphane örneğini ezberleyip ezberlemediğinizi değil, yöntemi yeni bir probleme taşıyıp taşıyamadığınızı görürü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 bir koda küçük bir özellik ekleyebilmeli,
  • Arama ve sıralama yöntemlerini duruma göre seçebilmeli,
  • Uç durumları assert ile doğrulayabilmeli,
  • Çözümünüzde seçtiğiniz veri yapısını ve maliyeti kısaca gerekçelendirebilmeli,
  • Aynı karar yöntemini daha önce görmediğiniz bir probleme uygulayabilmelisiniz.

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

Sistemdeki her kitabın şu alanları var:

  • 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. Kimliğiyle bir kitaba sık sık ulaşmak,
  3. Belirli kategorideki kitapları filtrelemek,
  4. Başlığa göre sıralı bir rapor hazırlamak,
  5. Ödünçteki kitap için öğrencileri geliş sırasıyla bekletmek.

Bu gereksinimlerin hepsini en iyi karşılayan tek bir veri yapısı yoktur.

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

Tablonun her satırında önce ihtiyaç, sonra ona uyan yapı var. Dönem boyunca hep bu sırayla düşündük: önce gereksinim, sonra seçim.

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

Bu indeks sayesinde bir kitabı kimliğiyle bulmak için listeyi her seferinde baştan taramamız gerekmez.

5 3. Kategoriye göre filtreleme

Bir kategorideki bütün kitapları bulmak için her kayda bakmak zorundayız. Bu yüzden listeyi baştan sona dolaşmak burada uygun bir seçimdir.

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 (ilk gelen önce) beklesin:

Burada yığın değil kuyruk gerekir, çünkü kitabı önce ilk gelen öğrenci almalı.

8 6. Aynı kayda iki yoldan ulaşmak

Aynı kitap sözlüğü hem books listesinde hem books_by_id sözlüğünde bulunabilir:

Değişiklik neden iki yerde de görünüyor? Çünkü iki koleksiyon da aynı kitap sözlüğünü gösteriyor.

Bu bazen işinize yarar: kitabı bir yerden güncellersiniz, iki yerde de güncel görünür. Ama elinde ayrı bir kopya olduğunu sanan programcı için hataya yol açabilir. Hangi değişkenin hangi nesneyi gösterdiğini aklınızda tutun.

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

Aşağıdaki kod, üzerine özellik ekleyeceğimiz küçük bir başlangıç sistemi:

Ş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. Kitap bekleyen bir öğrenciye verildiyse available değeri 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 tek bir örnekle denemek yetmez. Uç durumları da kontrol edin:

Bu testler üç durumu kapsar:

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

12 9. Kısa maliyet yorumu

Bu sistemdeki birkaç temel işlemin maliyetine bakalım:

12.1 Kimliğe göre kitap bulma

books_by_id.get(book_id) sözlükten değer okur. Bunu ortalama durumda O(1) kabul ederiz.

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() kuyruğun başındaki elemanı yaklaşık O(1) sürede alır.

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

sorted() genel amaçlı, verimli bir sıralama aracıdır. Yine de sıralamanın maliyeti veri boyutundan daha hızlı büyür, yani O(n)’den fazladır. Gerçek programlarda yerleşik sıralamayı kullanırız.

13 10. Mini karar tablosu

Tablonun son iki sütununu elinizle kapatın ve her satırı kendiniz doldurmaya ç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

14 11. Transfer görevi: destek talepleri sistemi

Şimdi kütüphane örneğini bırakıyoruz. Aşağıdaki problemi bu kitapta daha önce bir bütün olarak çözmedik.

Bir teknik destek sisteminin gereksinimleri şunlar:

  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ıralanmış bir rapor olarak görmek isteyecek.
  6. Yöneticinin yaptığı son değişiklik geri alınabilecek.

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

13. haftadaki yöntemle ticket ID ile erişim için kısa bir 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 kuralına uyar. Ama on binlerce talebin beklediği yoğun bir sistemde hangi satırdan şüphelenirsiniz, neden? Hangi Python yapısı daha uygun olur?

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 öneri hangi ön koşulu atlıyor? Açıklayın.

Important

Transfer görevinde ezberlenmiş bir kod aranmaz. Beklenen düşünme sırası şu:

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

15 Final için kendinizi kontrol edin

Aşağıdaki soruların her birini birkaç cümleyle cevaplayabiliyorsanız dersin temel konularını büyük ölçüde öğrenmişsiniz 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 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 kendi cümlelerinizle açıklayabilir misiniz?
  9. Bir veri yapısını seçerken hangi üç adımı izlemelisiniz?
  10. Çalışan bir çözümde bile veri yapısı seçiminin neden zayıf 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şler için uygundur.
  • Aynı alana göre tekrar tekrar arama yapılıyorsa bir indeks oluşturmak aramaları çok hızlandırabilir.
  • İki yapı aynı kaydı gösterebilir. Birinden yapılan değişiklik ötekinde de görünür.
  • Uç durumları assert ile denerseniz çözümünüze daha çok güvenebilirsiniz.
  • Finalde kodun ne yaptığını soran soruların yanında neden bu yapı ve neden bu algoritma? diye soran sorular da çıkar.
  • Transfer görevi, aynı düşünme biçimini daha önce görmediğiniz bir probleme uygulayıp uygulayamadığınızı ölçer.
Back to top