2013-07-26 40 views
53

ho qualche problema con una copia di listino:copia profonda una lista in Python

Quindi Dopo aver ottenuto E0 da 'get_edge', io faccio una copia di E0 chiamando 'E0_copy = list(E0)'. Qui indovino che E0_copy è una copia profonda di E0 e passo E0_copy in 'karger(E)'. Ma nella funzione principale.
Perché il risultato di 'print E0[1:10]' prima del ciclo for non è lo stesso con quello dopo il ciclo for?

Qui di seguito è il mio codice:

def get_graph(): 
    f=open('kargerMinCut.txt') 
    G={} 
    for line in f: 
     ints = [int(x) for x in line.split()] 
     G[ints[0]]=ints[1:len(ints)] 
    return G 

def get_edge(G): 
    E=[] 
    for i in range(1,201): 
     for v in G[i]: 
      if v>i: 
       E.append([i,v]) 
    print id(E) 
    return E 

def karger(E): 
    import random 
    count=200 
    while 1: 
     if count == 2: 
      break 
     edge = random.randint(0,len(E)-1) 
     v0=E[edge][0] 
     v1=E[edge][1]     
     E.pop(edge) 
     if v0 != v1: 
      count -= 1 
      i=0 
      while 1: 
       if i == len(E): 
        break 
       if E[i][0] == v1: 
        E[i][0] = v0 
       if E[i][1] == v1: 
        E[i][1] = v0 
       if E[i][0] == E[i][1]: 
        E.pop(i) 
        i-=1 
       i+=1 

    mincut=len(E) 
    return mincut 


if __name__=="__main__": 
    import copy 
    G = get_graph() 
    results=[] 
    E0 = get_edge(G) 
    print E0[1:10]    ## this result is not equal to print2 
    for k in range(1,5): 
     E0_copy=list(E0)   ## I guess here E0_coypy is a deep copy of E0 
     results.append(karger(E0_copy)) 
     #print "the result is %d" %min(results) 
    print E0[1:10]    ## this is print2 

Grazie in anticipo!

+1

Inoltre, b = a [:] è un co superficiale py. Consulta http://stackoverflow.com/questions/16270374/how-to-make-a-shallow-copy-of-a-list-in-python –

risposta

103

E0_copy non è una copia profonda. Non eseguire una copia profonda utilizzando list() (Entrambi list(...) e testList[:] sono copie poco profonde).

Si utilizza copy.deepcopy(...) per la copia profonda di un elenco.

deepcopy(x, memo=None, _nil=[]) 
    Deep copy operation on arbitrary Python objects. 

vedere il seguente frammento di codice -

>>> a = [[1, 2, 3], [4, 5, 6]] 
>>> b = list(a) 
>>> a 
[[1, 2, 3], [4, 5, 6]] 
>>> b 
[[1, 2, 3], [4, 5, 6]] 
>>> a[0][1] = 10 
>>> a 
[[1, 10, 3], [4, 5, 6]] 
>>> b # b changes too -> Not a deepcopy. 
[[1, 10, 3], [4, 5, 6]] 

ora vedere l'operazione deepcopy

>>> import copy 
>>> b = copy.deepcopy(a) 
>>> a 
[[1, 10, 3], [4, 5, 6]] 
>>> b 
[[1, 10, 3], [4, 5, 6]] 
>>> a[0][1] = 9 
>>> a 
[[1, 9, 3], [4, 5, 6]] 
>>> b # b doesn't change -> Deep Copy 
[[1, 10, 3], [4, 5, 6]] 
+1

Grazie. Ma ho pensato che l'elenco() è una copia profonda dall'ID (E0) non uguale a id (E0_copy). Potresti spiegare perché succede? L'elenco – Shen

+6

(...) non esegue ricorsivamente le copie degli oggetti interni. Fa solo una copia dell'elenco più esterno, facendo ancora riferimento alle liste interne dalla variabile precedente, quindi, quando si mutano le liste interne, il cambiamento si riflette sia nella lista originale che nella copia superficiale. –

+0

Puoi vedere che la copia superficiale fa riferimento agli elenchi interni controllando che id (a [0]) == id (b [0]) dove b = lista (a) e a è una lista di liste. –

1

Se il list elements sono immutable objects quindi è possibile utilizzare questo, altrimenti è necessario utilizzare deepcopy da copy modulo.

è possibile utilizzare anche il metodo più breve per copiare in profondità uno list come questo.

a = [0,1,2,3,4,5,6,7,8,9,10] 
b = a[:] #deep copying the list a and assigning it to b 
print id(a) 
20983280 
print id(b) 
12967208 

a[2] = 20 
print a 
[0, 1, 20, 3, 4, 5, 6, 7, 8, 9,10] 
print b 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10] 
+14

Questa non è una copia profonda. –

+1

Allora che cos'è. Ha due dizionari diversi (puoi controllare gli id ​​di ognuno) con gli stessi valori. –

+0

Leggi [this] (http://docs.python.org/2/library/copy.html), [:] crea solo una copia superficiale, non crea ricorsivamente copie degli oggetti all'interno di uno. –

0

solo una funzione di copia profonda ricorsiva.

def deepcopy(A): 
    rt = [] 
    for elem in A: 
     if isinstance(elem,list): 
      rt.append(deepcopy(elem)) 
     else: 
      rt.append(elem) 
    return rt 

Edit: Come accennato Cfreak, questo è già implementata nel modulo copy.

+2

Non c'è motivo di reimplementare la funzione standard 'deepcopy()' nel modulo 'copia' – Cfreak

0

Per quanto riguarda la lista come un albero, il deep_copy in Python può essere più compatto scritto come

def deep_copy(x): 
    if not isinstance(x, list): return x 
    else: return map(deep_copy, x) 
25

Credo che un sacco di programmatori hanno funzionato in uno o due problemi di intervista in cui si chiede di copia completa di un elenco collegato, tuttavia questo problema non è così facile come sembra!

in pitone, v'è un modulo chiamato "copia" con due funzioni utili

import copy 
copy.copy() 
copy.deepcopy() 

copia() è una funzione di copia superficiale, se l'argomento data è una struttura di dati composto, per esempio un elenco , allora pitone creerà un altro oggetto dello stesso tipo (in questo caso, un nuovo elenco ) ma per tutto dentro vecchia lista, solo viene copiato loro riferimento

# think of it like 
newList = [elem for elem in oldlist] 

Intuitivamente, si potrebbe supporre che deepcopy() sarebbe seguire lo stesso paradigma, e l'unica differenza è che per ogni elem avremo modo ricorsivo chiamare deepcopy, (proprio come la risposta di mbcoder)

ma questo è sbagliato!

deepcopy() effettivamente preservare la struttura grafica dei dati composto originale:

a = [1,2] 
b = [a,a] # there's only 1 object a 
c = deepcopy(b) 

# check the result 
c[0] is a # return False, a new object a' is created 
c[0] is c[1] # return True, c is [a',a'] not [a',a''] 

questa è la parte difficile, durante il processo di deepcopy() una tabella hash (dizionario in pitone) viene utilizzata per mappa: "ref old_object sul ref new_object", questo evitare inutili duplicati e quindi preservare la struttura dei dati copiati composti

official doc

-1

Questo è più divinatorio

my_list = [0, 1, 2, 3, 4, 5] # some list 
my_list_copy = list(my_list) # my_list_copy and my_list does not share reference now. 

NOTA: Questo non è al sicuro con un elenco dei tipi mutabili

+1

Questo non funziona. Pensavo che potesse essere solo controllato. Prova con un elenco di dizionari come buon esempio –

+0

@ShashankSingh sì, questo non funzionerà per un elenco di dizionari perché le voci sono tag di riferimento (che puntano a un percorso di memoria). Quindi la duplicazione di un elenco di dizionari con questo metodo creerà un nuovo elenco ma, poiché le voci sono dizionari, faranno comunque riferimento alla stessa posizione di memoria. –

3

Se il contenuto della lista sono i tipi di dati primitivi, è possibile utilizzare una comprensione

new_list = [i for i in old_list] 

è possibile nidificare per le liste multidimensionale come:

new_grid = [[i for i in row] for row in grid] 
Problemi correlati