How to deep copy a list?

Question

I have some problems with copying a list:

So after I got E0 from 'get_edge' , I make a copy of E0 by calling 'E0_copy = list(E0)' . Here, I think E0_copy is a deep copy of E0 , and I am E0_copy in 'karger(E)' . But in the main function.
Why does the result of 'print E0[1:10]' before the for loop not match the result after the for loop?

Below is my 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 

Answer 1

E0_copy not a deep copy. You do not make a deep copy with list() (Both list(...) and testList[:] are shallow copies).

You use copy.deepcopy(...) to deep copy the list.

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

See the following snippet -

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

Now view the deepcopy operation

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

Answer 2

I believe that many programmers face one or two interview problems when asked to deep copy a linked list, however this problem is more complicated than it seems!

python has a module called "copy" with two useful functions

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

copy () is a shallow copy function, if this argument is a composite data structure, for example, a list , then python will create another object of the same type (in this case, a new list ), but for everything inside the old list, only their link is copied

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

Intuitively, we could assume that deepcopy () will follow the same paradigm, and the only difference is that for each element we will recursively call deepcopy (same as mbcoder's answer)

But it's not right!

deepcopy () actually preserves the graphic structure of the original composite data:

 a = [1,2] b = [a,a] # there 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''] 

this is the difficult part, during the deepcopy () process a hash table (dictionary in python) is used for display: "old_object ref to new_object ref", this prevents unnecessary duplicates and thus preserves the structure of the copied compound data

official document

Answer 3

If the contents of the list is a primitive data type, you can use comprehension

 new_list = [i for i in old_list] 

You can nest it in multidimensional lists, for example:

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

Answer 4

If your list elements immutable objects , you can use it, otherwise you need to use the deepcopy module from copy .

you can also use the shortest path for a deep copy of a list like this.

 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] 

Answer 5

just a recursive deep copy function.

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

Edit: As Cfreak mentioned, this is already implemented in the copy module.

Answer 6

As for the list as a tree, deep_copy in python can be most compactly written as

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

Answer 7

It is more pythonic.

 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. 

NOTE: this is not safe with a list of mutable types