python - How to deep copy a list?

Question

I have some problem with a List copy:

So After I got E0 from 'get_edge', I make a copy of E0 by calling 'E0_copy = list(E0)'. Here I guess E0_copy is a deep copy of E0, and I pass E0_copy into 'karger(E)'. But in the main function.
Why does the result of 'print E0[1:10]' before the for loop is not the same with that 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 is not a deep copy. You don't make a deep copy using list() (Both list(...) and testList[:] are shallow copies).

You use copy.deepcopy(...) for deep copying a 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 see 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 a lot of programmers have run into one or two interview problems where they are asked to deep copy a linked list, however this problem is harder than it sounds!

in python, there is a module called "copy" with two useful functions

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

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

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

Intuitively, we could assume that deepcopy() would follow the same paradigm, and the only difference is that for each elem we will recursively call deepcopy, (just like the answer of mbcoder)

but this is wrong!

deepcopy() actually preserve the graphical structure of the original compound data:

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

this is the tricky part, during the process of deepcopy() a hashtable(dictionary in python) is used to map: "old_object ref onto new_object ref", this prevent unnecessary duplicates and thus preserve the structure of the copied compound data

official doc

Answer 3

If the contents of the list are primitive data types, you can use a comprehension

new_list = [i for i in old_list]

You can nest it for multidimensional lists like:

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

Answer 4

If your list elements are immutable objects then you can use this, otherwise you have to use deepcopy from copy module.

you can also use shortest way for deep copy 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

@Sukrit Kalra

No.1: list(), [:], copy.copy() are all shallow copy. If an object is compound, they are all not suitable. You need to use copy.deepcopy().

No.2: b = a directly, a and b have the same reference, changing a is even as changing b.

set a to b

if assgin a to b directly, a and b share one reference.

>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = a
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0] = 1
>>> a
[1, [4, 5, 6]]
>>> b
[1, [4, 5, 6]]


>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = 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
[[1, 10, 3], [4, 5, 6]]

shadow copy

by list()

list() and [:] are the same. Except for the first layer changes, all other layers' changes will be transferred.

>>> 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
>>> a
[1, [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]


>>> 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
[[1, 10, 3], [4, 5, 6]]

by [:]

>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = a[:]
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0] = 1
>>> a
[1, [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]


>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = 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
[[1, 10, 3], [4, 5, 6]]

list() and [:] change the other layers, except for the 1st layer

# =========== [:] ===========
>>> a = [[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b = a[:]
>>> a
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> a[0][2] = 4
>>> a
[[1, 2, 4], [4, 5, 6]]
>>> b
[[1, 2, 4], [4, 5, 6]]


>>> a = [[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b = a[:]
>>> a
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> a[0][2][0] = 999
>>> a
[[1, 2, [999, 6]], [4, 5, 6]]
>>> b
[[1, 2, [999, 6]], [4, 5, 6]]



# =========== list() ===========
>>> a = [[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b = list(a)
>>> a
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> a[0][2] = 4
>>> a
[[1, 2, 4], [4, 5, 6]]
>>> b
[[1, 2, 4], [4, 5, 6]]


>>> a = [[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b = list(a)
>>> a
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> b
[[1, 2, [3.5, 6]], [4, 5, 6]]
>>> a[0][2][0] = 999
>>> a
[[1, 2, [999, 6]], [4, 5, 6]]
>>> b
[[1, 2, [999, 6]], [4, 5, 6]]

by copy()

You will find that copy() function is the same as list() and [:]. They are all shallow copy.

For much more information about shallow copy and deep copy, maybe you can reference here.

>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = copy.copy(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
[[1, 10, 3], [4, 5, 6]]

by deepcopy()

>>> import copy
>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = copy.deepcopy(a)
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0] = 1
>>> a
[1, [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]


>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = copy.deepcopy(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
[[1, 2, 3], [4, 5, 6]]

Answer 6

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 copy module.

Answer 7

Here's an example of how to deep copy a 2D list:

  b = [x[:] for x in a]

Answer 8

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

def deep_copy(x):
    if not isinstance(x, list):
        return x
    else:
        return [deep_copy(elem) for elem in x]

It's basically recursively traversing the list in a depth-first way.

Answer 9

If you are not allowed to directly import modules you can define your own deepcopy function as -

def copyList(L):
if type(L[0]) != list:
    return [i for i in L]
else:
    return [copyList(L[i]) for i in range(len(L))]

It's working can be seen easily as -

>>> x = [[1,2,3],[3,4]]
>>> z = copyList(x)
>>> x
[[1, 2, 3], [3, 4]]
>>> z
[[1, 2, 3], [3, 4]]
>>> id(x)
2095053718720
>>> id(z)
2095053718528
>>> id(x[0])
2095058990144
>>> id(z[0])
2095058992192
>>>

Answer 10

This 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 referenced objects