...
Eroare Algoritmi și structuri de date · Capcane Python în algoritmi

nou = stare nu copiază lista: modifici „copia” și se schimbă și originalul

Pe scurt

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

Greșit
PYTHON
nou = stare
for i in range(1, len(stare) - 1):
    nou[i] = stare[i - 1] ^ stare[i + 1]
Corect
PYTHON
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

Greșit
PYTHON
anterior = [1] * m
for i in range(1, n):
    curent = anterior
    for j in range(1, m):
        curent[j] = curent[j - 1] + anterior[j]
Corect
PYTHON
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 = curent

Rândul curent trebuie să fie o listă nouă; altfel anterior[j] e deja suprascris.

3Salvarea unei stări pentru undo

Greșit
PYTHON
istoric.append(document)
document.append('text nou')
Corect
PYTHON
istoric.append(document[:])
document.append('text nou')

Fără copie, „starea salvată” se schimbă odată cu documentul.

Repară tu

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

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[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.

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

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