Coding Interview Prep · Ders

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.

4. ders / 413 adım

Not Alma: Özyinelemeli Sonuçları Önbelleğe Alma, CoddyKit'te ücretsiz bir Coding 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding 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=40

Sö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,21

Madeni 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))          # -1

Anı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 limit

Alan 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))  # 89

lru_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.

İnteraktif derste cevapla

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!

Başlamak ücretsiz

Yapay zeka eğitmeniyle Coding Interview Prep öğren — ücretsiz

Tarayıcında gerçek kod yaz ve çalıştır, 7/24 yapay zeka eğitmeninden anında yardım al; web'de ya da uygulamada kaldığın yerden devam et.

Kurslar: 90
Dersler: 360

Ücretsiz öğrenmeye başla Tüm kursu görüntüle

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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding 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. Coding 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.

Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?

Önceden deneyim gerekmez. CoddyKit'te Coding 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?

Evet. Her Coding 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

← Coding Interview Prep Sayfasına Dön