Memo greșit: cheia nu conține toți parametrii, iar rezultatul e greșit
Ai salvat în memo rezultatul doar după i (memo[i]), dar funcția depinde și de alt parametru (capacitate, j, suma rămasă), așa că un rezultat calculat pentru o stare e refolosit pentru alta. Cheia memo-ului trebuie să conțină toți parametrii care schimbă rezultatul: memo[(i, capacitate)].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Memoizarea e corectă doar dacă rezultatul funcției depinde numai de cheia memo-ului. Dacă funcția are doi parametri care se schimbă (i și capacitate, i și j, poziția și suma rămasă), iar tu salvezi doar memo[i], primul rezultat calculat pentru un i va fi refolosit pentru orice altă capacitate. Python nu dă nicio eroare: rezultatul e pur și simplu greșit, de obicei doar pe unele teste.
O variantă înrudită: un memo global, păstrat între apelurile pentru intrări diferite. Al doilea test primește rezultatele primului. Cu @lru_cache această problemă nu apare pentru argumente, pentru că toți parametrii fac parte automat din cheie, dar apare dacă funcția citește o variabilă globală care se schimbă.
În „Repară tu” testele folosesc assert, deci vezi AssertionError cu valoarea greșită.
De ce apare: cauzele frecvente
1Cheia ignoră un parametru
def rucsac(i, cap):
if i == len(greutati) or cap == 0:
return 0
if i in memo:
return memo[i]
best = rucsac(i + 1, cap)
if greutati[i] <= cap:
best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
memo[i] = best
return bestdef rucsac(i, cap):
if i == len(greutati) or cap == 0:
return 0
if (i, cap) in memo:
return memo[(i, cap)]
best = rucsac(i + 1, cap)
if greutati[i] <= cap:
best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
memo[(i, cap)] = best
return bestRezultatul pentru produsul i depinde de capacitatea rămasă. Tuplul (i, cap) face ca fiecare stare să aibă propria intrare în memo.
2Memo global refolosit pentru alte date
memo = {}
def drumuri(n):
...
print(drumuri_pe_harta(harta1))
print(drumuri_pe_harta(harta2))def drumuri_pe_harta(harta):
memo = {}
def drumuri(r, c):
...
return drumuri(0, 0)Memo-ul creat în funcția exterioară e nou pentru fiecare hartă, deci rezultatele nu se amestecă între teste.
Repară eroarea, direct în pagină
Funcția valoare_maxima(greutati, valori, capacitate) rezolvă problema rucsacului (fiecare produs o singură dată) cu memoizare, dar testele cu assert pică: memo-ul ține minte rezultatul doar după indicele produsului. Repar-o ca testele să treacă și să afișeze 9, 0 și 10.
def valoare_maxima(greutati, valori, capacitate):
memo = {}
def rucsac(i, cap):
if i == len(greutati):
return 0
if i in memo:
return memo[i]
best = rucsac(i + 1, cap)
if greutati[i] <= cap:
best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
memo[i] = best
return best
return rucsac(0, capacitate)
r = (valoare_maxima([1, 3, 4], [1, 4, 5], 7), valoare_maxima([5], [10], 4), valoare_maxima([5], [10], 5))
assert r == (9, 0, 10), f"memo gresit: {r}"
print(*r)9 0 10
Indiciu
Rezultatul depinde atât de produsul curent, cât și de capacitatea rămasă.
Reparația
def valoare_maxima(greutati, valori, capacitate):
memo = {}
def rucsac(i, cap):
if i == len(greutati):
return 0
if (i, cap) in memo:
return memo[(i, cap)]
best = rucsac(i + 1, cap)
if greutati[i] <= cap:
best = max(best, valori[i] + rucsac(i + 1, cap - greutati[i]))
memo[(i, cap)] = best
return best
return rucsac(0, capacitate)
r = (valoare_maxima([1, 3, 4], [1, 4, 5], 7), valoare_maxima([5], [10], 4), valoare_maxima([5], [10], 5))
assert r == (9, 0, 10), f"memo gresit: {r}"
print(*r)De ce merge
Funcția rucsac(i, cap) răspunde la întrebarea: cât pot câștiga din produsele de la i încolo, cu capacitatea cap? Răspunsul depinde de ambii parametri. Cu memo[i], rezultatul calculat pentru produsul 2 cu o anumită capacitate era refolosit pentru orice altă capacitate, deci se pierdeau combinații bune. Cu cheia (i, cap) fiecare stare are rezultatul ei: pentru capacitatea 7 cel mai bun e 3 + 4, cu valoarea 4 + 5 = 9.
Cum o eviți pe viitor
Înainte să adaugi memoizarea, scrie starea subproblemei: ce parametri determină complet răspunsul? Toți aceștia intră în cheie, ca tuplu. Variabilele care nu se schimbă (lista de intrare) nu intră în cheie, dar memo-ul trebuie creat din nou pentru fiecare intrare. Cel mai sigur: @lru_cache pe o funcție interioară, care include automat toți parametrii.
Întrebări frecvente
De ce primul test trece și al doilea nu?
La primul apel memo-ul e gol, deci rezultatele sunt calculate corect pentru stările întâlnite primele. Problemele apar când o stare nouă are aceeași cheie incompletă ca una veche, sau când memo-ul păstrează rezultate de la alt test.
Cum găsesc parametrii care trebuie să fie în cheie?
Uită-te la apelurile recursive: orice argument care diferă de la un apel la altul (nu doar i) face parte din stare. Dacă funcția citește o variabilă din afară care se schimbă, și aceea face parte din stare.
Erori înrudite
Recursivitatea fără memoizare rulează la nesfârșit: fib(40) nu se mai termină Funcția recursivă recalculează aceleași subprobleme de un număr exponențial de ori (fib(40) face sute de milioane de apeluri), așa că pare blocată și editorul o oprește după limita de timp. Salvează rezultatele: @lru_cache(maxsize=None) sau un dicționar memo. TypeError: unhashable type: 'list' cu @lru_cache @lru_cache folosește argumentele funcției ca cheie de dicționar, iar o listă nu poate fi cheie. Transmite un tuplu (tuple(lista)) sau, mai bine, păstrează lista în afara funcției memoizate și trimite doar indici. Argumentul implicit mutabil (rezultat=[]) păstrează valorile între apeluri Valoarea implicită a unui parametru (rezultat=[], memo={}) se creează o singură dată, când e definită funcția, și e aceeași listă la toate apelurile, așa că al doilea apel vede ce a adăugat primul. Folosește rezultat=None și creează lista în funcție: if rezultat is None: rezultat = []. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
