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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
functools.lru_cache (și @cache) salvează rezultatele într-un dicționar, cu argumentele apelului drept cheie. Cheile trebuie să aibă hash, adică să fie imuabile. Dacă funcția memoizată primește o listă, un dicționar sau un set, lru_cache nu poate construi cheia și aruncă TypeError: unhashable type: 'list', chiar la apel, înainte să se execute funcția.
În programarea dinamică, greșeala tipică este o funcție de forma f(valori, i), unde valori e lista de intrare. Soluția cea mai bună este ca lista să rămână în afara funcției memoizate: funcția interioară primește doar indici (f(i), f(i, j)), iar lista e accesată din funcția exterioară.
Dacă argumentul chiar se schimbă de la apel la apel (de exemplu starea curentă a unui joc), transformă-l în tuplu (tuple(stare)) sau în frozenset.
De ce apare: cauzele frecvente
1Lista de intrare trimisă funcției memoizate
from functools import lru_cache
@lru_cache(maxsize=None)
def profit(preturi, i):
if i >= len(preturi):
return 0
return max(profit(preturi, i + 1), preturi[i] + profit(preturi, i + 2))from functools import lru_cache
def profit_maxim(preturi):
@lru_cache(maxsize=None)
def profit(i):
if i >= len(preturi):
return 0
return max(profit(i + 1), preturi[i] + profit(i + 2))
return profit(0)Funcția memoizată primește doar indicele i, care e un întreg. Lista e citită din funcția exterioară și nu face parte din cheie.
2Starea ca listă
@lru_cache(maxsize=None)
def castiga(gramezi):
...
castiga([3, 4, 5])@lru_cache(maxsize=None)
def castiga(gramezi):
...
castiga((3, 4, 5))Un tuplu se poate folosi drept cheie. În interiorul funcției, stările noi se construiesc tot ca tupluri.
Repară eroarea, direct în pagină
Funcția jaf_maxim(case) calculează suma maximă pe care o poți lua din case alăturate pe o stradă, fără să iei două case vecine, cu programare dinamică memoizată. Codul dă TypeError: unhashable type: 'list'. Repar-o păstrând @lru_cache, ca să afișeze 12, 4 și 0.
from functools import lru_cache
@lru_cache(maxsize=None)
def castig(case, i):
if i >= len(case):
return 0
return max(castig(case, i + 1), case[i] + castig(case, i + 2))
def jaf_maxim(case):
return castig(case, 0)
print(jaf_maxim([2, 7, 9, 3, 1]))
print(jaf_maxim([4]))
print(jaf_maxim([]))12 4 0
Indiciu
Funcția memoizată nu trebuie să primească lista: mut-o într-o funcție interioară care primește doar indicele.
Reparația
from functools import lru_cache
def jaf_maxim(case):
@lru_cache(maxsize=None)
def castig(i):
if i >= len(case):
return 0
return max(castig(i + 1), case[i] + castig(i + 2))
return castig(0)
print(jaf_maxim([2, 7, 9, 3, 1]))
print(jaf_maxim([4]))
print(jaf_maxim([]))De ce merge
lru_cache construia cheia memo-ului din argumente, iar lista case nu poate fi cheie. Mutând funcția memoizată în interiorul lui jaf_maxim, ea vede lista din funcția exterioară și primește doar indicele i, un întreg. La fiecare casă alegi: o sari (castig(i + 1)) sau o iei și sari vecina (case[i] + castig(i + 2)). Pentru 2, 7, 9, 3, 1 cel mai bun e 2 + 9 + 1 = 12. Un memo nou se creează la fiecare apel al lui jaf_maxim.
Alte forme ale mesajului
TypeError: unhashable type: 'dict'TypeError: unhashable type: 'set'TypeError: cannot use 'list' as a dict key (unhashable type: 'list')
Cum o eviți pe viitor
La programarea dinamică top-down, separă datele de stare: datele fixe (lista, grila, textul) stau în funcția exterioară, iar funcția memoizată primește doar ce se schimbă, ca numere sau tupluri. Dacă ai nevoie de o listă ca stare, convertește-o la tuplu chiar la apel. Asta face și cheile memo-ului mai mici și mai rapide.
Întrebări frecvente
De ce nu primesc eroarea fără @lru_cache?
Fără decorator, funcția primește lista ca orice argument. Doar lru_cache are nevoie să o pună într-un dicționar ca cheie, de aceea eroarea apare abia după ce adaugi memoizarea.
Dacă lista e foarte lungă, tuplul nu e lent?
Da: la fiecare apel tuplul întreg ar fi hash-uit și comparat. De aceea varianta cu indici e mult mai bună: cheia e doar un număr.
Erori înrudite
TypeError: cannot use 'list' as a set element (unhashable type: 'list') Ai pus o listă (de exemplu o poziție [r, c] sau o combinație) într-un set sau ca cheie de dicționar. Listele se pot modifica, deci nu au hash. Folosește un tuplu: vizitate.add((r, c)) sau tuple(combinatie). 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. 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)]. Î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.
