Wie man eine Liste tief kopiert?

Ich habe ein Problem mit einer List-Kopie:

Nachdem ich E0 von 'get_edge' , mache ich eine Kopie von E0 indem ich 'E0_copy = list(E0)' . Hier denke ich, dass E0_copy eine tiefe Kopie von E0 ist und ich E0_copy in 'karger(E)' . Aber in der Hauptfunktion.
Warum ist das Ergebnis von 'print E0[1:10]' vor der for-Schleife nicht das gleiche wie nach der for-Schleife?

Unten ist mein Code:

 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 

   

E0_copy ist keine tiefe Kopie. Sie machen keine tiefe Kopie mit list() (Sowohl list(...) als auch testList[:] sind flache Kopien).

Sie verwenden copy.deepcopy(...) um eine Liste tief zu kopieren.

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

Sehen Sie sich das folgende Snippet an –

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

Sehen Sie sich jetzt den deepcopy Vorgang an

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

Ich glaube, dass viele Programmierer in ein oder zwei Interview-Probleme geraten sind, wo sie gebeten werden, eine verknüpfte Liste tief zu kopieren, aber dieses Problem ist nicht so einfach wie es klingt!

In Python gibt es ein Modul namens “copy” mit zwei nützlichen functionen

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

copy () ist eine flache Kopierfunktion, wenn das gegebene Argument eine zusammengesetzte Datenstruktur ist, zum Beispiel eine Liste , dann erstellt Python ein anderes Objekt des gleichen Typs (in diesem Fall eine neue Liste ), aber für alles innerhalb der alten Liste, nur ihre Referenz wird kopiert

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

Intuitiv könnten wir annehmen, dass deepcopy () demselben Paradigma folgen würde, und der einzige Unterschied ist, dass wir für jedes Element rekursiv decopy aufrufen (genau wie die Antwort von mbcoder).

aber das ist falsch!

deepcopy () behält die grafische Struktur der ursprünglichen zusammengesetzten Daten bei:

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

Dies ist der heikle Teil, während des processes decepy () wird eine Hashtabelle (Dictionary in Python) verwendet: “old_object ref auf new_object ref”, dies verhindert unnötige Duplikate und bewahrt somit die Struktur der kopierten zusammengesetzten Daten

offizielles Dokument

Wenn der Inhalt der Liste primitive Datentypen sind, können Sie ein Verständnis verwenden

 new_list = [i for i in old_list] 

Sie können es für mehrdimensionale Listen verschachteln wie:

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

Wenn Ihre list elements immutable objects , können Sie diese verwenden, andernfalls müssen Sie die deepcopy vom deepcopy .

Sie können auch den kürzesten Weg verwenden, um eine list wie diese tief zu kopieren.

 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] 

Hinsichtlich der Liste als Baum kann die deep_copy in Python am kompaktesten geschrieben werden

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

nur eine rekursive tiefe Kopierfunktion.

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

Edit: Wie bereits erwähnt, ist dies bereits im Kopiermodul implementiert.

Dies ist mehr Python

 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. 

Hinweis: Dies ist nicht sicher mit einer Liste von veränderbaren Typen