Comment copier en profondeur une liste?

J'ai un problème avec une copie de liste:

Donc, après mon E0départ 'get_edge', je fais une copie E0en appelant 'E0_copy = list(E0)'. Ici, je suppose que E0_copyc'est une copie profonde de E0, et je passe E0_copydans 'karger(E)'. Mais dans la fonction principale.
Pourquoi le résultat 'print E0[1:10]'avant la boucle for n'est-il pas le même que celui après la boucle for?

Voici mon 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_copyn'est pas une copie complète. Vous ne faites pas de copie profonde en utilisant list()(Les deux list(...)et testList[:]sont des copies superficielles).

Vous utilisez copy.deepcopy(...)pour copier en profondeur une liste.

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

Voir l'extrait suivant -

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

Maintenant voir l' deepcopyopération

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

Je pense que beaucoup de programmeurs ont rencontré un ou deux problèmes d'entretien où ils sont invités à copier en profondeur une liste chaînée, mais ce problème est plus difficile qu'il n'y paraît!

en python, il existe un module appelé "copie" avec deux fonctions utiles

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

copy () est une fonction de copie superficielle, si l'argument donné est une structure de données composée, par exemple une liste , alors python créera un autre objet du même type (dans ce cas, une nouvelle liste ) mais pour tout ce qui se trouve dans l'ancienne liste, seule leur référence est copiée

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

Intuitivement, nous pourrions supposer que deepcopy () suivrait le même paradigme, et la seule différence est que pour chaque élément, nous appellerons récursivement deepcopy , (tout comme la réponse de mbcoder)

mais c'est faux!

deepcopy () conserve en fait la structure graphique des données composées d'origine:

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

c'est la partie la plus délicate, pendant le processus de deepcopy () une table de hachage (dictionnaire en python) est utilisée pour mapper: "old_object ref sur new_object ref", cela évite les doublons inutiles et préserve ainsi la structure des données composées copiées

doc officiel

Si le contenu de la liste est des types de données primitifs, vous pouvez utiliser une compréhension

new_list = [i for i in old_list]

Vous pouvez l'imbriquer pour des listes multidimensionnelles comme:

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

Si votre list elementssont immutable objectsalors vous pouvez l' utiliser, sinon vous devez utiliser deepcopydu copymodule.

vous pouvez également utiliser le moyen le plus court pour une copie profonde listcomme celui-ci.

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]

juste une fonction de copie profonde récursive.

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

Edit: Comme Cfreak l'a mentionné, cela est déjà implémenté dans le copymodule.

En ce qui concerne la liste en tant qu'arbre, le deep_copy en python peut être écrit de la manière la plus compacte

def deep_copy(x):
    if not isinstance(x, list): return x
    else: return map(deep_copy, x)

Voici un exemple de la façon de copier en profondeur une liste:

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

C'est plus pythonique

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.

REMARQUE: ce n'est pas sûr avec une liste d'objets référencés