Sözlük tabanlı önbellek
- Algoritmalar kursu
- İleri seviye
- Ders 3/56
- 4 dk
Bir sözlük (dictionary) ile önbellek kurmayı öğrenirsin.
Sözlük tabanlı önbellek
Memoization önbelleği bir sözlük (dict) olarak uygulanır. Anahtar parametre, değer ise sonuçtur.
Sözlük, ortalama O(1) erişim sağlar; bu yüzden memoization verimli çalışır.
Parametre tuple ise sözlük anahtarı olabilir; çok boyutlu alt problemler için uygundur.
İlk hesap
İlk çağrıda hesap yapılır ve sonuç sözlüğe yazılır. Sonraki çağrılar doğrudan sözlükten okur.
Bu sayede karmaşık recursion'lar bile verimli hale gelir.
İlk hesabın maliyeti bir kez ödenir; geri kalan çağrılar düşük maliyetlidir.
Uygulama Memoized factorial
fact_memo(n, memo) yaz. Recursive factorial + memoization. print(fact_memo(5, {})) ile 120 yazdır.
Başlangıç kodu
def fact_memo(n, memo):
# Memoized factorialÖrnek çözüm
def fact_memo(n, memo):
# Memoized factorial
if n in memo:
return memo[n]
if n <= 1:
return 1
memo[n] = n * fact_memo(n - 1, memo)
return memo[n]
print(fact_memo(5, {}))Beklenen çıktı
120
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Sözlük tabanlı önbellek: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dict |
Sözlük |
key |
Parametre |
value |
Sonuç |
O(1) |
Hızlı |
2 Sözlük anahtarı neyi temsil eder?
- Alt problem parametresi Doğru cevap
- Sonuç
- Zaman
- Bellek
Açıklama: Alt problem parametresi.
3 Sözlük yazma
memo[____] = resultmemo[n] = resultAçıklama: n doğru.