nou = stare nu copiază lista: modifici „copia” și se schimbă și originalul
nou = stare nu creează o listă nouă, ci un al doilea nume pentru aceeași listă. Orice modificare prin nou se vede și prin stare. Copiază explicit: nou = stare[:] sau list(stare), iar pentru liste de liste [r[:] for r in stare].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
În Python, atribuirea b = a nu copiază nimic: leagă numele b de același obiect ca a. Pentru numere și texte nu contează, pentru că nu se modifică pe loc. Pentru liste, dicționare și set-uri, b[0] = 5 schimbă obiectul comun, deci și a[0] devine 5.
În algoritmi asta strică simulările „pas cu pas”, unde starea nouă trebuie calculată din starea veche: automate celulare, jocul vieții, relaxările din Bellman-Ford, DP cu două rânduri (anterior și curent). Dacă nou = stare, valorile deja actualizate sunt citite ca și cum ar fi vechi, iar rezultatul e greșit, fără nicio eroare.
Poți verifica cu nou is stare: dacă e True, nu ai o copie. Reparația: stare[:], list(stare), stare.copy(), iar pentru structuri imbricate, copierea fiecărui nivel sau copy.deepcopy.
De ce apare: cauzele frecvente
1Starea nouă e aceeași listă cu starea veche
nou = stare
for i in range(1, len(stare) - 1):
nou[i] = stare[i - 1] ^ stare[i + 1]nou = stare[:]
for i in range(1, len(stare) - 1):
nou[i] = stare[i - 1] ^ stare[i + 1]Cu copie, stare rămâne neschimbată cât timp calculezi pasul nou.
2DP cu două rânduri care devin același rând
anterior = [1] * m
for i in range(1, n):
curent = anterior
for j in range(1, m):
curent[j] = curent[j - 1] + anterior[j]anterior = [1] * m
for i in range(1, n):
curent = [1] * m
for j in range(1, m):
curent[j] = curent[j - 1] + anterior[j]
anterior = curentRândul curent trebuie să fie o listă nouă; altfel anterior[j] e deja suprascris.
3Salvarea unei stări pentru undo
istoric.append(document)
document.append('text nou')istoric.append(document[:])
document.append('text nou')Fără copie, „starea salvată” se schimbă odată cu documentul.
Repară eroarea, direct în pagină
Funcția pas(stare) calculează următoarea generație a unui șir de celule: fiecare celulă devine 1 dacă exact unul dintre vecini e 1 (capetele au vecin 0 în afară). Testul cu assert pică. Repar-o ca testele să treacă și să afișeze [0, 1, 0, 1, 0] și [1, 0, 0, 0, 1].
def pas(stare):
nou = stare
n = len(stare)
for i in range(n):
stanga = stare[i - 1] if i > 0 else 0
dreapta = stare[i + 1] if i < n - 1 else 0
nou[i] = stanga ^ dreapta
return nou
for stare, corect in [([0, 0, 1, 0, 0], [0, 1, 0, 1, 0]), ([0, 1, 0, 1, 0], [1, 0, 0, 0, 1])]:
rez = pas(stare)
assert rez == corect, f'generatie gresita: {rez}'
print(rez)[0, 1, 0, 1, 0] [1, 0, 0, 0, 1]
Indiciu
Calculează valorile noi într-o listă separată, nu în aceeași listă din care citești.
Reparația
def pas(stare):
nou = stare[:]
n = len(stare)
for i in range(n):
stanga = stare[i - 1] if i > 0 else 0
dreapta = stare[i + 1] if i < n - 1 else 0
nou[i] = stanga ^ dreapta
return nou
for stare, corect in [([0, 0, 1, 0, 0], [0, 1, 0, 1, 0]), ([0, 1, 0, 1, 0], [1, 0, 0, 0, 1])]:
rez = pas(stare)
assert rez == corect, f'generatie gresita: {rez}'
print(rez)De ce merge
Cu nou = stare, ambele nume arătau spre aceeași listă. Când celula 1 devenea 1, celula 2 citea deja valoarea nouă a vecinului din stânga, iar greșeala se propaga spre dreapta: [0, 1, 1, 1, 1]. Cu nou = stare[:], toate valorile noi se scriu într-o listă separată, iar fiecare celulă se calculează din generația veche, neatinsă.
Cum o eviți pe viitor
Când un algoritm are nevoie de „starea de dinainte” și „starea de după”, creează explicit o listă nouă pentru starea de după. Reține: = dă un nume nou, [:]/copy() dau o copie superficială, deepcopy copiază tot. Pentru liste de liste, copia superficială nu ajunge. Dacă un rezultat iese ciudat, verifică cu is ce variabile arată spre același obiect.
Întrebări frecvente
De ce cu numere nu am problema asta?
Și cu numere b = a dă același obiect, dar b += 1 creează un număr nou și leagă b de el. Listele se modifică pe loc, deci schimbarea se vede prin ambele nume.
Copia cu [:] e lentă?
E O(n), cât și calculul unui pas din simulare. Nu schimbă complexitatea algoritmului.
Erori înrudite
[[0] * m] * n: modifici o celulă și se schimbă toată coloana [[0] * m] * n nu creează n rânduri, ci n referințe la același rând, așa că dp[0][1] = 5 apare în toate rândurile. Creează fiecare rând separat: [[0] * m for _ in range(n)]. 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 = []. Backtracking-ul returnează liste goale: [[], [], []] Ai adăugat în rezultat chiar lista de lucru (rezultat.append(drum)), nu o copie a ei. La final backtracking-ul golește lista, deci toate intrările arată goale. Adaugă o copie: rezultat.append(drum[:]) sau list(drum). Î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.
