Jak głęboko skopiować listę?

150

Mam problem z kopią listy:

Więc po powrocie E0z 'get_edge', robię kopię E0, dzwoniąc 'E0_copy = list(E0)'. Myślę, że E0_copyjest to głęboka kopia E0i przechodzę E0_copydo 'karger(E)'. Ale w głównej funkcji.
Dlaczego wynik 'print E0[1:10]'przed pętlą for nie jest taki sam jak wynik po pętli for?

Poniżej mój kod:

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
Shen
źródło
2
Ponadto b = a [:] jest płytką kopią. Zapoznaj się ze stackoverflow.com/questions/16270374/…
Arvind Haran

Odpowiedzi:

231

E0_copynie jest głęboką kopią. Nie tworzysz głębokiej kopii za pomocą list()(Both list(...)i testList[:]są płytkie kopie).

Używasz copy.deepcopy(...)do głębokiego kopiowania listy.

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

Zobacz następujący fragment -

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

Teraz zobacz deepcopyoperację

>>> 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]]
Sukrit Kalra
źródło
3
Dzięki, ale pomyślałem, że lista () jest głęboką kopią, ponieważ id (E0) nie jest równe id (E0_copy). Czy mógłbyś wyjaśnić, dlaczego tak się stało?
Shen
15
list (...) nie tworzy rekurencyjnie kopii obiektów wewnętrznych. Tworzy tylko kopię listy najbardziej zewnętrznej, wciąż odwołując się do list wewnętrznych z poprzedniej zmiennej, dlatego po zmutowaniu list wewnętrznych zmiana jest odzwierciedlana zarówno na oryginalnej liście, jak i na płytkiej kopii.
Sukrit Kalra
1
Możesz zobaczyć, że płytkie kopiowanie odwołuje się do list wewnętrznych, sprawdzając ten identyfikator (a [0]) == id (b [0]), gdzie b = lista (a), a a jest listą list.
Sukrit Kalra
list1.append (list2) jest również płytką kopią list2
Lazik
60

Uważam, że wielu programistów napotkało jeden lub dwa problemy z rozmową kwalifikacyjną, podczas których proszono ich o dokładne skopiowanie połączonej listy, jednak ten problem jest trudniejszy niż się wydaje!

w Pythonie jest moduł o nazwie "kopia" z dwiema przydatnymi funkcjami

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

copy () jest funkcją płytkiego kopiowania, jeśli podany argument jest złożoną strukturą danych, na przykład listą , to python utworzy kolejny obiekt tego samego typu (w tym przypadku nową listę ), ale dla wszystkiego ze starej listy, kopiowane jest tylko ich odniesienie

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

Intuicyjnie moglibyśmy założyć, że deepcopy () będzie postępować zgodnie z tym samym paradygmatem, a jedyną różnicą jest to, że dla każdego elementu będziemy rekurencyjnie nazywać deepcopy (tak jak odpowiedź mbcoder)

ale to jest złe!

deepcopy () faktycznie zachowuje strukturę graficzną oryginalnych danych złożonych:

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

to jest trudna część, podczas procesu deepcopy () hashtable (słownik w Pythonie) jest używany do mapowania: "ref old_object ref na new_object ref", co zapobiega niepotrzebnym duplikatom, a tym samym zachowuje strukturę kopiowanych danych złożonych

oficjalny doc

watashiSHUN
źródło
18

Jeśli zawartość listy to prymitywne typy danych, możesz użyć zrozumienia

new_list = [i for i in old_list]

Możesz go zagnieżdżać dla list wielowymiarowych, takich jak:

new_grid = [[i for i in row] for row in grid]
aljgom
źródło
5

Jeśli list elementsimmutable objectsnastępnie można użyć tego, w przeciwnym razie trzeba korzystać deepcopyz copymodułu.

możesz również użyć najkrótszej drogi do głębokiego kopiowania, takiego listjak ten.

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
źródło
21
To nie jest głęboka kopia.
Sukrit Kalra
1
Więc co to jest. Ma dwa różne słowniki (możesz sprawdzić identyfikator każdego z nich) z tymi samymi wartościami.
tailor_raj
Przeczytaj to , [:] po prostu tworzy płytką kopię, nie tworzy rekurencyjnie kopii obiektów w środku.
Sukrit Kalra
1
Dzięki. masz na myśli to, że jeśli tego użyjemy, to nowa lista zostanie utworzona, ale wszystkie elementy nowej listy będą tylko kopiami, będą miały ten sam obiekt (ten sam identyfikator) co poprzednia?
tailor_raj
Spróbuj użyć listy zagnieżdżonej. Zaktualizuj zagnieżdżony element listy a. Zostanie również zaktualizowany na liście b. Oznacza to, że [:] nie jest głęboką kopią.
AnupamChugh
2

po prostu rekurencyjna funkcja głębokiego kopiowania.

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

Edycja: Jak wspomniał Cfreak, jest to już zaimplementowane w copymodule.

rnbguy
źródło
4
Nie ma powodu, aby ponownie deepcopy()copy
zaimplementować
1

Jeśli chodzi o listę jako drzewo, deep_copy w Pythonie można najbardziej zwięźle zapisać jako

def deep_copy(x):
    if not isinstance(x, list): return x
    else: return map(deep_copy, x)
ShellayLee
źródło
0

Oto przykład, jak głęboko skopiować listę:

  b = [x[:] for x in a]
AnupamChugh
źródło
0

To jest bardziej pytoniczne

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.

UWAGA: Nie jest to bezpieczne w przypadku listy obiektów, do których istnieją odniesienia

Kwaw Annor
źródło
2
To nie działa. Myślałem, że to może tylko sprawdzić. Wypróbuj listę słowników jako dobry przykład
Shashank Singh,
@ShashankSingh tak, to nie zadziała dla listy słowników, ponieważ wpisy są znacznikami referencyjnymi (wskazującymi na lokalizację pamięci). Zatem powielenie listy słowników tą metodą utworzy nową listę, ale ponieważ wpisy są słownikami, będą nadal odnosić się do tej samej lokalizacji pamięci.
Kwaw Annor,