У меня проблема с копией списка:
После того как я получил E0
от 'get_edge'
я сделать копию E0
по телефону 'E0_copy = list(E0)'
. Здесь я предполагаю, E0_copy
что это глубокая копия E0
, и я перехожу E0_copy
к ней 'karger(E)'
. Но в main function.
Почему результат 'print E0[1:10]'
до цикла for не совпадает с результатом после цикла for?
Ниже мой код:
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
не глубокая копия. Вы не делаете глубокую копию, используяlist()
(Обаlist(...)
иtestList[:]
являются мелкими копиями).Вы используете
copy.deepcopy(...)
для глубокого копирования списка.deepcopy(x, memo=None, _nil=[]) Deep copy operation on arbitrary Python objects.
См. Следующий фрагмент -
>>> 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]]
Теперь посмотрим на
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]]
источник
copy.deepcopy
это невероятно медленно по сравнению с нарезкой списка (примерно в 20 раз). Реализация__deepcopy__
в классе может немного ускорить его.Я считаю, что многие программисты сталкивались с одной или двумя проблемами на собеседовании, когда их просили глубоко скопировать связанный список, однако эта проблема сложнее, чем кажется!
в python есть модуль под названием «копия» с двумя полезными функциями
import copy copy.copy() copy.deepcopy()
copy () - это функция поверхностного копирования, если данный аргумент является составной структурой данных, например, списком , тогда python создаст другой объект того же типа (в данном случае новый список ), но для всего внутри старого списка, копируется только их ссылка
# think of it like newList = [elem for elem in oldlist]
Интуитивно мы могли бы предположить, что deepcopy () будет следовать той же парадигме, с той лишь разницей, что для каждого элемента мы будем рекурсивно вызывать deepcopy (точно так же, как ответ mbcoder)
но это неправильно!
deepcopy () фактически сохраняет графическую структуру исходных составных данных:
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'']
это сложная часть, во время процесса deepcopy () используется хеш-таблица (словарь в Python) для отображения: «old_object ref на new_object ref», это предотвращает ненужные дублирования и, таким образом, сохраняет структуру скопированных составных данных
официальный документ
источник
Если содержимое списка является примитивными типами данных, вы можете использовать понимание
new_list = [i for i in old_list]
Вы можете вложить его в многомерные списки, например:
new_grid = [[i for i in row] for row in grid]
источник
Если у вас
list elements
есть,immutable objects
вы можете использовать это, в противном случае вам придется использоватьdeepcopy
fromcopy
module.вы также можете использовать кратчайший путь для глубокого копирования
list
подобного этому.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]
источник
просто рекурсивная функция глубокого копирования.
def deepcopy(A): rt = [] for elem in A: if isinstance(elem,list): rt.append(deepcopy(elem)) else: rt.append(elem) return rt
Изменить: как упоминалось в Cfreak, это уже реализовано в
copy
модуле.источник
deepcopy()
функцию вcopy
модулеЧто касается списка в виде дерева, deep_copy в Python можно наиболее компактно записать как
def deep_copy(x): if not isinstance(x, list): return x else: return map(deep_copy, x)
источник
Вот пример того, как глубоко скопировать 2D-список:
b = [x[:] for x in a]
источник
a = [3, 4, 5] b = [x[:] for x in a] Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<stdin>", line 1, in <listcomp> TypeError: 'int' object is not subscriptable
Это более питонический
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.
ПРИМЕЧАНИЕ: это небезопасно со списком ссылочных объектов.
источник