RuntimeError: deque mutated during iteration
Ai adăugat sau scos elemente dintr-un deque în timp ce îl parcurgeai cu for. Pentru o coadă BFS nu parcurge cu for: folosește while coada: nod = coada.popleft(), iar vecinii noi îi adaugi cu append.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
for x in coada parcurge un deque cu un iterator care verifică, la fiecare pas, dacă deque-ul a fost modificat. Dacă între timp ai făcut append, appendleft, pop sau popleft, iteratorul se oprește cu RuntimeError: deque mutated during iteration.
În algoritmi apare aproape mereu la BFS: cineva scrie for nod in coada: și adaugă vecinii în aceeași coadă. Cu o listă obișnuită codul „merge” (lista acceptă append în timpul parcurgerii), de aceea greșeala apare abia după ce treci la deque.
Coada se consumă cu while coada: și popleft(): fiecare nod e scos o singură dată, iar vecinii adăugați sunt procesați la rândul lor. Linia din stivă arată for-ul, nu append-ul care a modificat coada.
De ce apare: cauzele frecvente
1BFS cu for peste coadă
coada = deque([start])
for nod in coada:
for v in vecini[nod]:
coada.append(v)coada = deque([start])
while coada:
nod = coada.popleft()
for v in vecini[nod]:
coada.append(v)while verifică doar dacă mai sunt elemente; popleft scoate nodul curent fără un iterator care să se strice.
2Ștergere în timpul parcurgerii
for x in fereastra:
if x < prag:
fereastra.remove(x)fereastra = deque(x for x in fereastra if x >= prag)Construiește un deque nou cu elementele păstrate în loc să-l modifici pe cel parcurs.
3Procesare pe niveluri
for nod in coada:
coada.popleft()
...for _ in range(len(coada)):
nod = coada.popleft()
...range(len(coada)) fixează numărul de noduri al nivelului curent înainte de modificări.
Repară eroarea, direct în pagină
Funcția ordine_bfs(start, vecini) trebuie să dea ordinea în care BFS-ul vizitează stațiile. Codul parcurge coada cu for și dă RuntimeError: deque mutated during iteration. Repar-o ca să afișeze A B C D E.
from collections import deque
def ordine_bfs(start, vecini):
coada = deque([start])
vazut = {start}
ordine = []
for nod in coada:
ordine.append(nod)
for v in vecini[nod]:
if v not in vazut:
vazut.add(v)
coada.append(v)
return ordine
vecini = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': []}
print(' '.join(ordine_bfs('A', vecini)))A B C D E
Indiciu
Folosește while coada: și scoate nodul curent cu coada.popleft().
Reparația
from collections import deque
def ordine_bfs(start, vecini):
coada = deque([start])
vazut = {start}
ordine = []
while coada:
nod = coada.popleft()
ordine.append(nod)
for v in vecini[nod]:
if v not in vazut:
vazut.add(v)
coada.append(v)
return ordine
vecini = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': [], 'E': []}
print(' '.join(ordine_bfs('A', vecini)))De ce merge
Iteratorul unui deque se oprește cu eroare dacă deque-ul se modifică în timpul parcurgerii, iar BFS-ul adaugă vecini exact atunci. Cu while coada: nu există un iterator: la fiecare pas scoți primul nod cu popleft() și adaugi vecinii la coadă. Ordinea rămâne cea a BFS-ului: întâi A, apoi vecinii lui, apoi vecinii vecinilor.
Alte forme ale mesajului
RuntimeError: deque mutated during iterationRuntimeError: dictionary changed size during iteration
Cum o eviți pe viitor
Tratează o coadă ca pe o coadă, nu ca pe o listă: o golești cu while coada: și popleft(). Dacă ai nevoie de nivelurile BFS, fixează dimensiunea nivelului cu range(len(coada)) înainte de a scoate. Pentru filtrare, construiește o structură nouă. Aceeași regulă se aplică dicționarelor și set-urilor.
Întrebări frecvente
De ce cu o listă nu primesc eroarea?
Iteratorul listei doar crește un index și nu verifică modificările. BFS-ul cu for nod in lista și append chiar funcționează, dar lista nu se golește niciodată și ține tot în memorie.
Pot parcurge o copie: for nod in list(coada)?
Nu dă eroare, dar nodurile adăugate în timpul parcurgerii nu sunt procesate. Pentru BFS ai nevoie de while.
Erori înrudite
BFS-ul nu se mai oprește pe un graf cu ciclu (lipsesc nodurile vizitate) BFS-ul pune în coadă vecinii fără să verifice dacă au mai fost descoperiți, iar pe un graf cu ciclu (sau neorientat) aceleași noduri intră în coadă la nesfârșit; editorul oprește programul după limita de timp. Marchează nodul ca vizitat când îl pui în coadă. IndexError: pop from an empty deque Ai apelat coada.popleft() (sau pop()) pe un deque gol: bucla a continuat după ce coada s-a golit, sau ai scos de două ori pentru un singur element pus. Folosește while coada: și scoate un singur element pe iterație. 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, []). Î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.
