DSA Interview Prep · Oppitunti

Memoisaatio: rekursiivisten tulosten välimuistitus

Soveltakaa @functools.lru_cachea ja manuaalisia memo-sanakirjoja Fibonacci- ja climbing-stairs-tehtäviin eksponentiaalisen uudelleenlaskennan poistamiseksi.

Oppitunti 4/413 vaihetta

Memoisaatio: rekursiivisten tulosten välimuistitus on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.

Turhien rekursiivisten kutsujen ongelma

Naiivi rekursiivinen Fibonacci laskee samat arvot toistuvasti. fib(5) kutsuu funktioita fib(4) ja fib(3); fib(4) kutsuu funktioita fib(3) ja fib(2) — joten fib(3) lasketaan kahdesti. Tämä päällekkäisyys kasvaa eksponentiaalisesti: fib(40) tekee yli miljardi funktiokutsua. Memoisaatio ratkaisee ongelman tallentamalla kunkin tuloksen ensimmäisellä laskentakerralla, jolloin myöhemmät kutsut hakevat tuloksen ajassa O(1) sen uudelleen laskemisen sijaan.

# 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

Manuaalinen memoisaatio dictin avulla

Lisätkää memo-sanakirja parametriksi (tai sulkeumaan). Tarkistakaa ennen laskemista, onko vastaus jo memossa. Jos on, palauttakaa se heti. Jos ei, laskekaa vastaus, tallentakaa se memoon ja palauttakaa se. Jokainen yksilöllinen osatehtävä lasketaan nyt täsmälleen kerran, jolloin aikavaativuus muuttuu arvosta O(2^n) arvoon O(n) ja tilavaativuus on O(n) memo-sanakirjalle sekä O(n) pinotilaa.

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-dekorattori

Python tarjoaa @functools.lru_cache(maxsize=None)-dekorattorin (saatavilla Python 3.9:stä alkaen myös muodossa @functools.cache), joka automatisoi memoisaation. Kun tämä dekorattori lisätään funktion yläpuolelle, kaikki kutsut tallennetaan välimuistiin argumenttien perusteella. maxsize=None tarkoittaa rajoittamatonta välimuistin kokoa — jokainen yksilöllinen argumenttiyhdistelmä tallennetaan välimuistiin. Näin mikä tahansa rekursiivinen funktio voidaan muuttaa memoisoiduksi versioksi yhdellä koodirivillä.

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=...)

Climbing Stairs (LeetCode 70)

LeetCode 70 ”Climbing Stairs”: voitte nousta kerrallaan yhden tai kaksi porrasta. Kuinka monella tavalla pääsette portaalle n? Tämä on Fibonacci piilotetussa muodossa: ways(n) = ways(n-1) + ways(n-2). Perustapaukset ovat ways(0) = 1 (on yksi tapa pysyä lähtötasolla) ja ways(1) = 1. Memoisaatiolla aikavaativuus on O(n) ja tilavaativuus O(n).

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

Coin Change (LeetCode 322)

LeetCode 322 ”Coin Change”: kun annettuna ovat kolikkojen nimellisarvot ja tavoitesumma, etsikää kolikoiden pienin mahdollinen lukumäärä. Ylhäältä alas etenevässä memoisoidussa rekursiossa käytetään lauseketta dp(amount) = 1 + min(dp(amount - coin)) jokaiselle kelvolliselle kolikolle. Perustapaus on dp(0) = 0. Tallentakaa jokainen osasumma välimuistiin. Jos osasummaa ei voida muodostaa, palauttakaa ääretön. Memoisaatio muuttaa eksponentiaalisen raakavoimaratkaisun aikavaativuudeksi O(amount × len(coins)).

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

Word Break (LeetCode 139) memoisaatiolla

LeetCode 139 ”Word Break”: selvittäkää, voidaanko merkkijono jakaa sanakirjan sanoiksi. Ylhäältä alas etenevä rekursio: can_break(s, start) kokeilee jokaista etuliitettä s[start:end]; jos etuliite löytyy sanakirjasta ja can_break(s, end) palauttaa arvon true, palauttakaa true. Ilman memoisaatiota aikavaativuus on O(2^n); memoisaation avulla (tallentamalla jokaisen aloitusindeksin tulos välimuistiin) se muuttuu muotoon O(n² × L), jossa L on sanan enimmäispituus.

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

Memoisaatio vs. taulukointi

Memoisaatio (ylhäältä alas) aloittaa alkuperäisestä ongelmasta ja tallentaa vastaukset välimuistiin sitä mukaa kuin ne löydetään rekursiivisesti. Se ratkaisee vain aidosti tarvittavat osatehtävät. Taulukointi (alhaalta ylöspäin) täyttää taulukon pienistä osatehtävistä suuriin ja ratkaisee kaikki osatehtävät tarpeesta riippumatta. Memoisaatio on helpompi johtaa rekursiivisesta ratkaisusta, kun taas taulukointi välttää rekursion syvyysrajoitukset ja funktiokutsujen kustannukset.

# 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

Tilankäytön optimointi: liukuvat muuttujat

Monet DP-ongelmat, jotka memoisoitu rekursio ratkaisee tilavaativuudella O(n), voidaan optimoida edelleen tilavaativuuteen O(1), kun tarvitaan vain kiinteä määrä aiempien osatehtävien vastauksia. Fibonacci-luvussa merkitsevät vain kaksi viimeisintä arvoa. Sama pätee portaiden kiipeämiseen. Kahden liukuvan muuttujan käyttö korvaa koko memo-sanakirjan tai taulukon.

# 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 vs. sulkeuma vs. globaali sanakirja

Memoisaation voi toteuttaa manuaalisesti kolmella tavalla. Globaali sanakirja on yksinkertainen, mutta saastuttaa moduulin nimiavaruuden. Sulkeuma kapseloi välimuistin funktion sisään, estää sen vuotamisen muualle, mutta vaatii käärefunktion. @lru_cache on siistein ratkaisu — yksi dekorattori korvaa kaiken toistuvan pohjakoodin. Haastattelutilanteessa aloittakaa @lru_cache-ratkaisusta, ellei haastattelija nimenomaisesti pyydä manuaalista toteutusta.

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

Milloin memoisaatiosta ei ole hyötyä

Memoisaatio nopeuttaa vain ongelmia, joissa on päällekkäisiä osatehtäviä — tilanteita, joissa sama osatehtävä lasketaan useita kertoja. Jos jokainen osatehtävä on yksilöllinen (kuten yksinkertaisessa puun läpikäynnissä, jossa jokainen solmu käydään läpi täsmälleen kerran), memoisaatio lisää kustannuksia ilman hyötyä. Memoisaatio ei myöskään voi korjata ongelmia, joissa rekursiopuu on eksponentiaalinen erillisten osatehtävien lukumäärän suhteen eikä siksi, että osatehtäviä käytettäisiin uudelleen — tällaiset ongelmat vaativat kokonaan toisen algoritmin.

# 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')

Yhteenveto: memoisaation tarkistuslista

Käyttäkää memoisaatiota, kun rekursiivinen ratkaisunne on oikea mutta hidas turhien uudelleenlaskentojen vuoksi, funktiolla on vain vähän yksilöllisiä argumenttiyhdistelmiä ja palautusarvo riippuu ainoastaan argumenteista (puhdas funktio — ei sivuvaikutuksia eikä globaalia tilaa). Tarkistakaa osatehtävien tila-avaruus: jos yksilöllisiä tiloja on enintään O(n) tai O(n²), memoisaatio muuttaa eksponentiaalisen aikavaativuuden polynomiseen muotoon.

Pikatarkistus

Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteiden ymmärtämistä.

Vastaa interaktiivisessa oppitunnissa

Oppitunnin kertaus

Tässä oppitunnissa opitte, että memoisaatio tallentaa osatehtävien tulokset uudelleenlaskennan välttämiseksi ja muuttaa eksponentiaalisen rekursion polynomiseksi aikavaativuudeksi, @functools.lru_cache on idiomaattinen Python-työkalu, jonka käyttöön tarvitaan vain yksi koodirivi ja memoisaatio (ylhäältä alas) ja taulukointi (alhaalta ylöspäin) ovat DP:n kaksi toteutustapaa — memoisaatio on helpompi johtaa, kun taas taulukointi välttää pinon syvyysongelmat. Onnittelut — olette suorittaneet rekursio- ja hajautustaulumoduulit!

Aloita maksutta

Opi Python tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 30
Oppitunnit: 120

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Memoisaatio: rekursiivisten tulosten välimuistitus” ilmainen?

Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Memoisaatio: rekursiivisten tulosten välimuistitus”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Memoisaatio: rekursiivisten tulosten välimuistitus”?

Soveltakaa @functools.lru_cachea ja manuaalisia memo-sanakirjoja Fibonacci- ja climbing-stairs-tehtäviin eksponentiaalisen uudelleenlaskennan poistamiseksi. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Memoisaatio: rekursiivisten tulosten välimuistitus”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä DSA Interview Prep-oppitunnilla?

Kyllä. Jokainen DSA Interview Prep-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

Rekursion rakenne: perustapaus, luottamus, rakentaminen
Kutsupinon visualisointi
Rekursiivisten ja iteroivien ratkaisujen kompromissit
Memoisaatio: rekursiivisten tulosten välimuistitus

← Takaisin: DSA Interview Prep