Как глубоко скопировать список?

159

У меня проблема с копией списка:

После того как я получил 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
Шен
источник
2
Кроме того, b = a [:] - неглубокая копия. Обратитесь к stackoverflow.com/questions/16270374/…
Арвинд Харан,

Ответы:

246

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]]
Сукрит Калра
источник
3
Спасибо, но я думал, что list () - это глубокая копия, поскольку id (E0) не равен id (E0_copy). Не могли бы вы объяснить, почему это произошло?
Шен
15
list (...) не рекурсивно копирует внутренние объекты. Он делает копию только самого внешнего списка, по-прежнему ссылаясь на внутренние списки из предыдущей переменной, поэтому, когда вы изменяете внутренние списки, изменение отражается как в исходном списке, так и в неглубокой копии.
Sukrit Kalra
1
Вы можете видеть, что поверхностное копирование ссылается на внутренние списки, проверяя этот id (a [0]) == id (b [0]), где b = list (a), а a - список списков.
Sukrit Kalra
list1.append (list2) также является мелкой копией list2
Lazik
Имейте в виду, что copy.deepcopyэто невероятно медленно по сравнению с нарезкой списка (примерно в 20 раз). Реализация__deepcopy__ в классе может немного ускорить его.
ggorlen
65

Я считаю, что многие программисты сталкивались с одной или двумя проблемами на собеседовании, когда их просили глубоко скопировать связанный список, однако эта проблема сложнее, чем кажется!

в 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», это предотвращает ненужные дублирования и, таким образом, сохраняет структуру скопированных составных данных

официальный документ

ваташи
источник
Документы deepcopy должны быть обновлены, чтобы на видном месте включить предупреждение / пример в конце этого ответа.
примерно
20

Если содержимое списка является примитивными типами данных, вы можете использовать понимание

new_list = [i for i in old_list]

Вы можете вложить его в многомерные списки, например:

new_grid = [[i for i in row] for row in grid]
Aljgom
источник
5

Если у вас list elementsесть, immutable objectsвы можете использовать это, в противном случае вам придется использовать deepcopyfrom copymodule.

вы также можете использовать кратчайший путь для глубокого копирования 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]
tailor_raj
источник
21
Это не Глубокая копия.
Sukrit Kalra
1
Тогда что это. Он имеет два разных словаря (вы можете проверить идентификаторы каждого из них) с одинаковыми значениями.
tailor_raj
Прочтите это , [:] просто создает неглубокую копию, он не рекурсивно создает копии объектов внутри нее.
Sukrit Kalra
1
Спасибо. вы хотите сказать, что если мы используем это, новый список будет создан, но все элементы нового списка будут только копиями, они будут иметь тот же объект (тот же идентификатор), что и предыдущий?
tailor_raj
1
Попробуйте использовать вложенный список. Обновите вложенный элемент списка a. Он также будет обновлен в списке b. Это означает, что [:] не является полной копией.
AnupamChugh,
2

просто рекурсивная функция глубокого копирования.

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

Изменить: как упоминалось в Cfreak, это уже реализовано в copyмодуле.

rnbguy
источник
4
Нет причин повторно реализовывать стандартную deepcopy()функцию в copyмодуле
Cfreak
1

Что касается списка в виде дерева, deep_copy в Python можно наиболее компактно записать как

def deep_copy(x):
    if not isinstance(x, list): return x
    else: return map(deep_copy, x)
ShellayLee
источник
0

Вот пример того, как глубоко скопировать 2D-список:

  b = [x[:] for x in a]
АнупамЧью
источник
1
Вы тестировали этот пример? 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
Стеф
Ах, я написал это для 2D-списков. а = [[0,1], [2,3]]. Я отредактировал ответ, чтобы выделить это.
AnupamChugh,
-1

Это более питонический

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.

ПРИМЕЧАНИЕ: это небезопасно со списком ссылочных объектов.

Kwaw Annor
источник
2
Это не работает. Я думал, может, но только что проверил. Попробуйте использовать список словарей в качестве хорошего примера
Шашанк Сингх
@ShashankSingh да, это не сработает для списка словарей, потому что записи являются ссылочными тегами (указывающими на ячейку памяти). Таким образом, при дублировании списка словарей с помощью этого метода будет создан новый список, но, поскольку записи являются словарями, они по-прежнему будут ссылаться на одно и то же место в памяти.
Kwaw Annor