Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma
Üstel yeniden hesaplamayı ortadan kaldırmak için Fibonacci ve merdiven tırmanma problemlerinde @functools.lru_cache ile elle oluşturulan not sözlüklerini uygulayın.
Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 4. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Gereksiz Özyineleme Sorunu
Naif özyinelemeli Fibonacci aynı değerleri tekrar tekrar hesaplar. fib(5), fib(4) ve fib(3) çağrılarını yapar; fib(4) ise fib(3) ve fib(2) çağrılarını yapar — dolayısıyla fib(3) iki kez hesaplanır. Bu gereksizlik üstel olarak büyür: fib(40), bir milyardan fazla işlev çağrısı yapar. Anımsama, her sonucu ilk hesaplandığında saklayarak bu sorunu çözer; sonraki çağrılar sonucu yeniden hesaplamak yerine O(1) zamanda alır.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40Sözlükle El ile Önbelleğe Alma
Parametre olarak (veya bir kapanım içinde) bir memo sözlüğü ekleyin. Hesaplamadan önce yanıtın önbellekte olup olmadığını kontrol edin. Varsa hemen döndürün. Yoksa hesaplayın, önbelleğe kaydedin ve döndürün. Artık her benzersiz alt problem tam olarak bir kez hesaplanır; böylece zaman karmaşıklığı O(2^n)'den O(n)'e dönüşür ve önbellek sözlüğü için O(n) alanın yanı sıra O(n) yığın alanı kullanılır.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!functools.lru_cache Dekoratörü
Python, anımsamayı otomatikleştirmek için @functools.lru_cache(maxsize=None) (Python 3.9 ve sonrasında @functools.cache olarak da kullanılabilir) sunar. Bu dekoratörü bir işlevin üzerine eklemek, tüm çağrıları bağımsız değişkenlerine göre önbelleğe alır. maxsize=None, önbellek boyutunun sınırsız olduğu, yani her benzersiz bağımsız değişken birleşiminin önbelleğe alındığı anlamına gelir. Böylece herhangi bir özyinelemeli işlev, tek bir kod satırıyla önbelleğe alınmış bir sürüme dönüştürülebilir.
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)Merdiven Çıkma (LeetCode 70)
LeetCode 70 'Merdiven Çıkma': Her seferinde 1 veya 2 basamak çıkabilirsiniz. n'inci basamağa ulaşmanın kaç yolu vardır? Bu, kılık değiştirmiş bir Fibonacci problemidir: ways(n) = ways(n-1) + ways(n-2). Temel durumlar: ways(0) = 1 (zeminde kalmanın tek yolu vardır), ways(1) = 1. Anımsama ile zaman karmaşıklığı O(n), alan karmaşıklığı O(n) olur.
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21Madeni Para Değişimi (LeetCode 322)
LeetCode 322 'Madeni Para Değişimi': Madeni para değerleri ve bir hedef miktar verildiğinde, gereken en az madeni para sayısını bulun. Üstten alta, anımsamalı özyineleme: her geçerli madeni para için dp(amount) = 1 + min(dp(amount - coin)). Temel durum: dp(0) = 0. Her alt miktarı önbelleğe alın. Bir alt miktara ulaşılamıyorsa sonsuzluk döndürün. Anımsama, üstel kaba kuvvet yaklaşımını O(hedef miktar × madeni para sayısı) zaman karmaşıklığına dönüştürür.
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1Anımsama ile Sözcük Ayırma (LeetCode 139)
LeetCode 139 'Sözcük Ayırma': Bir dizenin sözlükteki sözcüklere ayrılıp ayrılamayacağını belirleyin. Üstten alta özyineleme, her s[start:end] ön ekini dener; bu ön ek sözlükteyse ve can_break(s, end) doğruysa true döndürür. Önbellek olmadan zaman karmaşıklığı O(2^n)'dir; önbellekle (her başlangıç indisini saklayarak) L'nin en uzun sözcük uzunluğu olduğu O(n² × L) düzeyine iner.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # FalseÖnbelleğe Alma ve Tablolama
Önbelleğe alma (üstten alta), özgün problemle başlar ve yanıtları özyinelemeli olarak keşfedildikçe önbelleğe kaydeder. Yalnızca gerçekten gereken alt problemleri çözer. Tablolama (alttan üste), küçük alt problemlerden büyüklere doğru bir tabloyu önceden doldurur ve gereken alt problemlerin tümünü çözer. Önbelleğe almayı özyinelemeli bir çözümden türetmek daha kolaydır; tablolama ise özyineleme derinliği sınırlarını ve işlev çağrısı ek yükünü ortadan kaldırır.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limitAlan Optimizasyonu: Kayan Değişkenler
Anımsamalı özyinelemenin O(n) alan kullandığı birçok DP problemi, yalnızca sabit sayıda önceki alt problem sonucuna ihtiyaç duyulduğunda O(1) alana kadar daha da iyileştirilebilir. Fibonacci için yalnızca son iki değer önemlidir. Merdiven çıkma problemi için de durum aynıdır. İki kayan değişken, önbellek sözlüğünün veya tablonun tamamının yerini alır.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache ve Kapanım ve Genel Sözlük
Anımsamayı el ile uygulamanın üç yolu vardır. Genel sözlük basittir; ancak modül kapsamını kirletir. Kapanım, önbelleği işlev içinde kapsüller ve dışarı sızmasını önler; ancak bir sarmalayıcı gerektirir. @lru_cache en temiz seçenektir — tüm kalıp kodun yerini tek bir dekoratör alır. Bir mülakat bağlamında, mülakat yapan kişi özellikle el ile gerçekleştirmenizi istemediği sürece @lru_cache ile başlayın.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040Önbelleğe Almanın Yararlı Olmadığı Durumlar
Önbelleğe alma yalnızca örtüşen alt problemlere sahip problemleri hızlandırır — yani aynı alt problemin birden çok kez hesaplandığı durumları. Her alt problem benzersizse (her düğümün tam olarak bir kez ziyaret edildiği basit ağaçta gezinmede olduğu gibi), önbelleğe alma yarar sağlamadan ek yük getirir. Ayrıca özyineleme ağacı, yeniden kullanımdan ziyade farklı alt problemlerin sayısına göre üstel olan problemleri de önbelleğe alma çözemez — bu problemler bütünüyle farklı bir algoritma gerektirir.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')Özet: Önbelleğe Alma Kontrol Listesi
Şu durumlarda anımsamayı uygulayın: Gereksiz yeniden hesaplama nedeniyle yavaş olan ancak doğru bir özyinelemeli çözümünüz varsa, işlevin az sayıda farklı bağımsız değişken birleşimi varsa ve dönüş değeri yalnızca bağımsız değişkenlere bağlıysa (yan etkisi ve genel durumu olmayan saf işlev). Alt problem durum uzayını kontrol edin: En fazla O(n) veya O(n²) farklı durum varsa, anımsama üstel zamanı polinom zamana dönüştürür.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: anımsama, yeniden hesaplamayı önlemek için alt problemlerin sonuçlarını saklar ve üstel özyinelemeyi polinom zamana dönüştürür, @functools.lru_cache yalnızca bir satır gerektiren, Python'a özgü tercih edilen araçtır ve anımsama (üstten alta) ile tablolama (alttan üste), DP'nin iki biçimidir — anımsamayı türetmek daha kolaydır, tablolama ise yığın derinliği sorunlarını ortadan kaldırır. Tebrikler — özyineleme ve karma tablo modüllerini tamamladınız!
Sıkça Sorulan Sorular
“Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma” dersi ücretsiz mi?
Evet — “Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma” dersinde ne öğreneceğim?
Üstel yeniden hesaplamayı ortadan kaldırmak için Fibonacci ve merdiven tırmanma problemlerinde @functools.lru_cache ile elle oluşturulan not sözlüklerini uygulayın. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 4. dersidir.
“Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Özyineleme Çerçevesi: Temel Durum, Güven, Oluşturma
- Çağrı Yığınını Görselleştirme
- Özyinelemeli ve Yinelemeli Yaklaşımların Ödünleşimleri
- Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma