RuntimeError: dictionary changed size during iteration
Parcurgi un dicționar (de obicei graful) cu for, iar în buclă adaugi sau ștergi chei. Cu defaultdict, chiar și citirea graf[v] pentru un nod nou adaugă o cheie. Parcurge list(graf) sau citește cu graf.get(v, []).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Python nu permite schimbarea numărului de chei ale unui dicționar în timp ce îl parcurgi: ordinea internă s-ar putea schimba, iar bucla ar sări sau ar repeta chei. În loc de un rezultat imprevizibil, primești RuntimeError: dictionary changed size during iteration, la linia cu for.
La grafuri, capcana tipică este defaultdict. Ai construit graful cu defaultdict(list) și acum parcurgi nodurile: for nod in graf: for v in graf[nod]: ... graf[v] .... Dacă v nu era cheie (un nod fără muchii de ieșire), simpla citire graf[v] creează cheia cu o listă goală, deci dicționarul s-a modificat în timpul buclei.
Alte cauze: ștergi noduri dintr-un dicționar de grade (sortarea topologică) chiar în bucla care îl parcurge, sau adaugi intrări noi într-un memo în timp ce îl parcurgi.
De ce apare: cauzele frecvente
1defaultdict creează chei la citire
from collections import defaultdict
grad = defaultdict(int)
graf = defaultdict(list, {'a': ['b']})
for nod in graf:
for v in graf[nod]:
grad[v] += 1
print(graf[v])from collections import defaultdict
grad = defaultdict(int)
graf = defaultdict(list, {'a': ['b']})
for nod in list(graf):
for v in graf[nod]:
grad[v] += 1
print(graf.get(v, []))graf.get(v, []) citește fără să creeze cheia. list(graf) face o copie a cheilor, deci bucla nu mai depinde de dicționarul modificat.
2Ștergi chei în bucla pe dicționar
for nod in grad:
if grad[nod] == 0:
del grad[nod]grad = {nod: g for nod, g in grad.items() if g != 0}Construiește un dicționar nou cu cheile păstrate, sau parcurge list(grad) dacă vrei neapărat să ștergi din original.
Repară eroarea, direct în pagină
Funcția grade_intrare(graf) calculează câte muchii intră în fiecare nod al unui graf orientat construit cu defaultdict(list). Codul dă RuntimeError: dictionary changed size during iteration. Repar-o ca să afișeze {'curs': 0, 'teme': 1, 'examen': 2}.
from collections import defaultdict
def grade_intrare(graf):
grad = {}
for nod in graf:
grad.setdefault(nod, 0)
for v in graf[nod]:
grad[v] = grad.get(v, 0) + 1
if not graf[v]:
grad.setdefault(v, 0)
return grad
graf = defaultdict(list)
graf['curs'] += ['teme', 'examen']
graf['teme'] += ['examen']
print(grade_intrare(graf)){'curs': 0, 'teme': 1, 'examen': 2}Indiciu
Citirea graf[v] pe un defaultdict adaugă cheia v dacă lipsește; parcurge o copie a cheilor.
Reparația
from collections import defaultdict
def grade_intrare(graf):
grad = {}
for nod in list(graf):
grad.setdefault(nod, 0)
for v in graf.get(nod, []):
grad[v] = grad.get(v, 0) + 1
return grad
graf = defaultdict(list)
graf['curs'] += ['teme', 'examen']
graf['teme'] += ['examen']
print(grade_intrare(graf))De ce merge
Nodul 'examen' nu avea cheie în graf. Citirea graf[v] pe defaultdict o crea cu o listă goală chiar în timp ce bucla parcurgea dicționarul, iar Python oprea bucla. Varianta corectă parcurge list(graf), o copie fixă a cheilor, și citește vecinii cu get, care nu creează chei. Gradul nodului 'examen' apare oricum din muchiile care intră în el.
Alte forme ale mesajului
RuntimeError: Set changed size during iterationRuntimeError: dictionary keys changed during iteration
Cum o eviți pe viitor
Cât timp parcurgi un dicționar cu for, nu adăuga și nu șterge chei. Dacă ai nevoie, parcurge list(d) sau list(d.items()). Cu defaultdict, citește nodurile care pot lipsi cu get sau in, nu cu [ ]. O soluție sigură: după construirea grafului, transformă-l în dicționar obișnuit cu toate nodurile ca chei (graf = {n: graf.get(n, []) for n in noduri}).
Întrebări frecvente
Dar doar am citit graf[v], nu am scris nimic. De ce se schimbă dicționarul?
La defaultdict, citirea unei chei care lipsește apelează fabrica (list) și salvează rezultatul ca valoare nouă. E o scriere ascunsă în spatele unei citiri.
Pot modifica valorile, fără să schimb cheile?
Da. d[cheie] = valoare_noua pentru o cheie existentă sau d[cheie].append(x) nu schimbă numărul de chei, deci bucla continuă normal.
Erori înrudite
RuntimeError: Set changed size during iteration Ai adăugat sau ai șters elemente dintr-un set în timp ce îl parcurgeai cu for. Python oprește bucla, pentru că ordinea internă a set-ului se schimbă. Parcurge o copie (for x in list(multime)) sau construiește un set nou. KeyError: 'D' la graf[nod] (nodul nu are listă de vecini) Graful e un dicționar de liste de vecini, dar un nod apare doar ca vecin, nu și ca cheie (de obicei un nod fără muchii de ieșire). graf[nod] dă KeyError. Folosește graf.get(nod, []) sau construiește graful cu defaultdict(list) și adaugă toate nodurile. IndexError: list index out of range după del lista[i] în buclă Ștergi elemente din listă în timp ce o parcurgi cu for i in range(len(lista)). Lista se scurtează, dar range-ul a fost calculat la început, așa că i ajunge dincolo de capăt. Construiește o listă nouă cu elementele păstrate sau parcurge lista de la coadă. Î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.
