...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

TypeError: unhashable type: 'list' cu @lru_cache

Pe scurt

@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

Greșit
PYTHON
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))
Corect
PYTHON
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ă

Greșit
PYTHON
@lru_cache(maxsize=None)
def castiga(gramezi):
    ...

castiga([3, 4, 5])
Corect
PYTHON
@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ă tu

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.

Codul care dă eroarea
PYTHON
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([]))
După reparație, programul afișează
12
4
0
Indiciu

Funcția memoizată nu trebuie să primească lista: mut-o într-o funcție interioară care primește doar indicele.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

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