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
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]]
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]
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.
Here's an example of how to deep copy a 2D list:
b = [x[:] for x in a]
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]
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
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
>>>
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 map(deep_copy, x)
@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
.
$ python
Python 3.9.0 (tags/v3.9.0:9cf6752, Oct 5 2020, 15:34:40) [MSC v.1927 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 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]]
>>> exit()
$ python
Python 3.9.0 (tags/v3.9.0:9cf6752, Oct 5 2020, 15:34:40) [MSC v.1927 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 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]]
>>> exit()
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
Source: Stackoverflow.com