Memoisointi vastaan taulukointi
Kaksi tapaa välimuistittaa osaongelmien vastaukset
Memoisointi vastaan taulukointi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Miksi tuloksia kannattaa välimuistittaa
Naivi rekursio tekee saman työn yhä uudelleen. Dynaaminen ohjelmointi tallentaa jokaisen vastauksen kerran, joten sitä ei tarvitse laskea uudelleen.
fib(40) # slow: recomputes endlesslyPäällekkäiset osaongelmat
DP:tä käytetään, kun ongelma jakautuu päällekkäisiin osaongelmiin. Sama pienempi tapaus esiintyy rekursion monissa haaroissa.
fib(5) needs fib(3) twiceYlhäältä alas: memoization
Memoization on tavallista rekursiota, johon on lisätty välimuisti. Laskette arvot tarpeen mukaan ja muistatte tuloksen, kun syöte kohdataan ensimmäisen kerran.
memo = {}Helppo memoization Pythonissa
lru_cache-dekoraattori muuttaa hitaan rekursion nopeaksi DP:ksi yhdellä rivillä ja tallentaa kaikkien kutsujen tulokset automaattisesti.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Alhaalta ylös: tabulointi
Tabulointi täyttää taulukon pienimmistä tapauksista kohti vastausta silmukan avulla rekursion sijaan.
dp = [0] * (n + 1)Taulukoitu Fibonacci
Asettakaa perustapaukset ja antakaa sitten jokaisen solun lukea arvot, jotka on jo laskettu. Kutsupinoa ei tarvita, vaan selkeä silmukka riittää.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Sama vastaus, eri tyyli
Memoization ja tabulointi ratkaisevat saman palautuskaavan. Ne eroavat vain etenemissuunnassa: ylhäältä alas tarpeen mukaan tai alhaalta ylös järjestyksessä.
Milloin memoization kannattaa valita
Valitkaa memoization, kun palautuskaava on luonteva kirjoittaa ja kaikkia tiloja ei välttämättä tarvita.
Milloin tabulointi kannattaa valita
Valitkaa tabulointi tiukkoihin silmukoihin, rekursion syvyysrajojen aiheuttamien virheiden välttämiseksi ja silloin, kun koko taulukko lasketaan joka tapauksessa.
import sys; sys.setrecursionlimit(10**6)Huomioikaa rekursion syvyysraja
Syvä memoization-rekursio voi saavuttaa Pythonin rekursion syvyysrajan ja kaatua ajonaikaiseen virhetuomioon suurilla syötteillä.
Molemmilla on sama kustannus
Kummassakin tapauksessa nopeutus perustuu siihen, että jokainen tila ratkaistaan kerran. Kokonaisaika on tilojen määrä kerrottuna yhden tilan käsittelyyn kuluvalla työmäärällä.
Pikatarkistus
Kumpi lähestymistapa täyttää taulukon alhaalta ylös silmukan avulla?
Kertaus: kaksi tietä, yksi DP
Osaatte nyt välimuistittaa osaongelmat kahdella tavalla. Memoization etenee rekursiivisesti ylhäältä alas, kun taas tabulointi käy tilat läpi silmukalla alhaalta ylös. Valitkaa se, jonka rakenne on selkeämpi. ✨
Opi Valmistautuminen ohjelmointihaastatteluihin 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
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Memoisointi vastaan taulukointi” ilmainen?
Kyllä – oppitunnin ”Memoisointi vastaan taulukointi” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Memoisointi vastaan taulukointi”?
Kaksi tapaa välimuistittaa osaongelmien vastaukset Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Memoisointi vastaan taulukointi”-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ä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-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
- Memoisointi vastaan taulukointi
- Tilan ja siirtymän määrittäminen
- Portaiden kiipeäminen ja kolikkokombinaatiot
- Pisin kasvava alijono